Submission #306130

---

Source Code Expand

#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <string>
#include <string.h>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <map>
#include <set>
#include <iostream>
#include <sstream>
#include <cctype>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rrep(i,n) for(int i = 1; i <= n; ++i)
#define drep(i,n) for(int i = n-1; i >= 0; --i)
#define gep(i,g,j) for(int i = g.head[j]; i != -1; i = g.e[i].next)
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcount
#define snuke srand((unsigned)clock()+(unsigned)time(NULL))
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef vector<int> vi;

const int MX = 100005, INF = 1000010000;
const ll LINF = 1000000000000000000ll;
const double eps = 1e-10;
const int di[] = {-1,0,1,0}, dj[] = {0,-1,0,1}; //^<v>

// Max flow
struct Maxflow {
  int n;
  vector<int> to, lim, next, head, dist, it;
  Maxflow(){}
  Maxflow(int n):n(n),head(n,-1),it(n){}
  void addEdge(int a, int b, int c=1) {
    next.push_back(head[a]); head[a] = to.size(); to.push_back(b); lim.push_back(c);
    next.push_back(head[b]); head[b] = to.size(); to.push_back(a); lim.push_back(0); 
  }
  void addEdge2(int a, int b, int c=1) {
    next.push_back(head[a]); head[a] = to.size(); to.push_back(b); lim.push_back(c);
    next.push_back(head[b]); head[b] = to.size(); to.push_back(a); lim.push_back(c); 
  }
  void bfs(int sv){
    dist = vector<int>(n,INF);
    queue<int> q;
    dist[sv] = 0; q.push(sv);
    while(!q.empty()){
      int v = q.front(); q.pop();
      for(int i = head[v]; i != -1; i = next[i]) {
        if(lim[i] && dist[to[i]] == INF){
          dist[to[i]] = dist[v]+1; q.push(to[i]);
        }
      }
    }
  }
  int dfs(int v, int tv, int nf=INF){
    if(v == tv) return nf;
    for(; it[v] != -1; it[v] = next[it[v]]){
      int u = to[it[v]], f;
      if(!lim[it[v]] || dist[v] >= dist[u]) continue;
      if(f = dfs(u, tv, min(nf, lim[it[v]])), f){
        lim[it[v]] -= f;
        lim[it[v]^1] += f;
        return f;
      }
    }
    return 0;
  }
  int solve(int sv, int tv){
    int flow = 0, f;
    while(1){
      bfs(sv);
      if(dist[tv] == INF) return flow;
      rep(i,n) it[i] = head[i];
      while(f = dfs(sv,tv), f) flow += f;
    }
  }
  int nex(int v, int m) {
    for(int i = head[v]; i != -1; i = next[i]) {
      if(lim[i] && to[i] != v+m) return to[i];
    }
    puts("not found");
    return -1;
  }
};
//

int h, w;
string s[55];
int dist[55][55];

void bfss(int si, int sj) {
  queue<P> q;
  rep(i,h)rep(j,w) dist[i][j] = INF;
  dist[si][sj] = 0;
  q.push(P(si,sj));
  while(q.size()) {
    int i = q.front().fi, j = q.front().se; q.pop();
    rep(v,4) {
      int ni = i+di[v], nj = j+dj[v];
      if (ni<0||nj<0||ni>=h||nj>=w||s[ni][nj]=='#') continue;
      if (dist[ni][nj] != INF) continue;
      dist[ni][nj] = dist[i][j]+1;
      q.push(P(ni,nj));
    }
  }
}

int main(){
  cin >> h >> w;
  rep(i,h) cin >> s[i];
  int n = h*w, sv, tv = n*2, av, bv;
  rep(i,h)rep(j,w) if (s[i][j] == 'S') sv = i*w+j;
  rep(i,h)rep(j,w) if (s[i][j] == 'A') av = i*w+j;
  rep(i,h)rep(j,w) if (s[i][j] == 'B') bv = i*w+j;
  bfss(sv/w,sv%w);
  Maxflow mf(n*2+2);
  rep(i,n) {
    if (i == sv) mf.addEdge(i,n+i,2);
    else mf.addEdge(i,n+i);
  }
  rep(k,n) {
    int i = k/w, j = k%w;
    if (s[i][j] == '#') continue;
    rep(v,4) {
      int ni = i+di[v], nj = j+dj[v];
      if (ni<0||nj<0||ni>=h||nj>=w||s[ni][nj]=='#') continue;
      int nv = ni*w+nj;
      if (dist[i][j] < dist[ni][nj]) {
        mf.addEdge(n+k,nv);
      }
    }
  }
  //rep(i,h){rep(j,w) printf("%2d ",min(99,dist[i][j]));puts("");}
  mf.addEdge(n+av,tv);
  mf.addEdge(n+bv,tv);
  if (mf.solve(sv,tv) != 2) {
    puts("NA");
    return 0;
  }
  {
    int i = av/w, j = av%w;
    while(s[i][j] != 'S') {
      int v = i*w+j;
      int nx = mf.nex(v,n)-n;
      i = nx/w; j = nx%w;
      if (s[i][j] == 'S') break;
      s[i][j] = 'a';
    }
  }
  {
    int i = bv/w, j = bv%w;
    while(s[i][j] != 'S') {
      int v = i*w+j;
      int nx = mf.nex(v,n)-n;
      i = nx/w; j = nx%w;
      if (s[i][j] == 'S') break;
      s[i][j] = 'b';
    }
  }
  rep(i,h) cout << s[i] << endl; 
  return 0;
}

Submission Info

Judge Result