Submission #306263

---

Source Code Expand

#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <sstream>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <cstdlib>

#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define iter(a) __typeof(a.begin())
#define FOR(it,a) for(iter(a)it=a.begin();it!=a.end();++it)
#define F first
#define S second
#define SZ(a) (int)((a).size())
#define sz(a) SZ(a)
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define ALL(a) (a).begin(),(a).end()
using namespace std;

typedef long long ll;
typedef pair<int,int> PI;
typedef unsigned long long ull;

#define PR(...) do{cerr << "line : " << __LINE__ << endl; pr(#__VA_ARGS__, __VA_ARGS__);}while(0);
template<class T>
void pr(const string& name, T t){
  cerr << name << ": " << t << endl;
}

template<typename T, typename ... Types>
void pr(const string& names, T t, Types ... rest) {
  auto comma_pos = names.find(',');
  cerr << names.substr(0, comma_pos) << ": " << t << ", ";
  
  auto next_name_pos = names.find_first_not_of(" \t\n", comma_pos + 1);
  pr(string(names, next_name_pos), rest ...);
}

template<class T,class U> ostream& operator<< (ostream& o, const pair<T,U>& v){return o << "(" << v.F << ", " << v.S << ")";}
template<class T> ostream& operator<< (ostream& o, const vector<T>& v){o << "{";rep(i,SZ(v)) o << (i?", ":"") << v[i];return o << "}";}

const int dx[] = {0,1,0,-1};
const int dy[] = {-1,0,1,0};
#define endl '\n'



int n,m;
string in[100];
int cost[100][100];
bool ok[100][100];

struct FlowGraphF{
  /*
    verified
    http://poj.org/problem?id=3713  <- uso kaiho de tukatta
   */
  
  struct edge{
    int to,cap,rev;
    bool revf;
    edge(int to,int cap,int rev,bool revf=false):to(to),cap(cap),rev(rev),revf(revf){};
  };
  
  vector<vector<edge> > G;
  vector<int> vis;
  
  void add_edge(int from,int to,int cap){
    G[from].push_back(edge(to,cap,G[to].size()));
    G[to].push_back(edge(from,0,G[from].size()-1,true));
  }
  bool fflag;
  FlowGraphF(int V):G(V),vis(V),fflag(false){};
  char fc;
  
  int dfs(int v,int t,int f){
    if(v == t) return f;
    vis[v] = 1;
    int cx = v/2/m;
    int cy = v/2%m;
    if(v%2==0 && cx < n && cy < m){
      if(in[cx][cy]=='A') fc = 'a';
      if(in[cx][cy] == 'B') fc = 'b';
    }
    
    for(int i = 0; i < (int)G[v].size(); ++i){
      edge& e = G[v][i];
      if(e.cap > 0 && !vis[e.to]){
        int d = dfs(e.to, t, min(f, e.cap));
        if(d > 0){
          e.cap -= d;
          G[e.to][e.rev].cap += d;
          
          if(1){
            if(v + 1 == e.to && v%2==0){
              int cx = (v/2)/m;
              int cy = (v/2)%m;
              
              if(cx < n && cy < m && in[cx][cy] == '.')
                ok[cx][cy] = 1;
            }
            // else if(e.to + 1 == v && e.to%2==0){
            //   int cx = (v/2)/m;
            //   int cy = (v/2)%m;
            //   if(cx < n && cy < m){
            //     assert(false);
            //     if(in[cx][cy] == 'a') in[cx][cy] = 'b';
            //     else if(in[cx][cy] == 'b') in[cx][cy] = 'a';
            //   }
            // }
          }
          
          return d;
        }
      }
    }
    return 0;
  }
  
  int max_flow(int s, int t, int sum=-1){
    int flow = 0;
    if(sum == -1){
      sum = 0;
      for(int i = 0; i < (int)G[s].size(); ++i)
        sum += G[s][i].cap;
    }
    
    for(;sum > 0;){
      fill(vis.begin(), vis.end(), 0);
      int f = dfs(s, t, sum);
      if(f == 0) break;
      fflag = true;
      flow += f;
      sum -= f;
    }
    return flow;
  }

  void dfs2(int v,int t){
    if(v == t) return;
    int cx = v/2/m;
    int cy = v/2%m;
    if(v%2==0 && cx < n && cy < m){
      if(in[cx][cy]=='A'){
        fc = 'a';
        return;
      }
      if(in[cx][cy] == 'B'){
        fc = 'b';
        return;
      }
      
    }
    
    //PR(v);
    
    for(int i = 0; i < (int)G[v].size(); ++i){
      edge& e = G[v][i];
      if(e.revf) continue;
      if(e.cap == 0){
        int nx = e.to/2/m;
        int ny = e.to/2%m;
        dfs2(e.to, t);
        
        if(1){
          if(v + 1 == e.to && v%2==0){
            int cx = (v/2)/m;
            int cy = (v/2)%m;
            if(cx < n && cy < m && in[cx][cy] == '.')
              in[cx][cy] = fc;
          }else if(e.to + 1 == v && e.to%2==0){
            int cx = (v/2)/m;
            int cy = (v/2)%m;
            assert(false);
            if(cx < n && cy < m){
              if(in[cx][cy] == 'a') in[cx][cy] = 'b';
              else if(in[cx][cy] == 'b') in[cx][cy] = 'a';
            }
          }
        }
      }
    }
  }  
  
  void dfsfill(int source, int target){
    dfs2(source,target);
  }
};


int main(int argc, char *argv[])
{
  cin >> n >> m;
  rep(i,n) cin >> in[i];
  queue<pair<int,PI> > q;
  rep(i,n)rep(j,m){
    if(in[i][j] == 'S') q.push(mp(0,mp(i,j)));
  }

  memset(cost,-1,sizeof(cost));
  
  while(!q.empty()){
    int cc = q.front().F;
    int cx = q.front().S.F;
    int cy = q.front().S.S;
    q.pop();
    if(cost[cx][cy] != -1) continue;
    cost[cx][cy] = cc;
    
    rep(i,4){
      int nx = cx + dx[i];
      int ny = cy + dy[i];
      if(nx < 0 || nx >= n || ny < 0 || ny >= m || in[nx][ny] == '#')
        continue;
      q.push(mp(cc+1,mp(nx,ny)));
    }
  }

  FlowGraphF fg(n*m*2+10);
  int source = n*m*2;
  int target1 = source + 1;
  int target2 = target1 + 1;
  int target = target2+1;
  
  fg.add_edge(target1,target,1);
  fg.add_edge(target2,target,1);
  vector<int> nidx(n);
  vector<int> midx(m);
  rep(i,n) nidx[i] = i;
  rep(j,m) midx[j] = j;

  srand(time(NULL));
  random_shuffle(ALL(nidx));
  random_shuffle(ALL(midx));
  
  //rep(i,n){
  for(auto i : nidx){
    random_shuffle(ALL(midx));
    for(auto j : midx){
      //rep(j,m){
      int inidx = (i*m+j)*2;
      int outidx = inidx + 1;
      if(in[i][j] == '#') continue;
      if(in[i][j] == 'S'){
        fg.add_edge(source,outidx,2);
      }
      if(in[i][j] == 'A'){
        fg.add_edge(outidx,target1,1);
      }
      if(in[i][j] == 'B'){
        fg.add_edge(outidx,target2,1);
      }
      fg.add_edge(inidx,outidx,1);
      
      rep(k,4){
        int nx = i + dx[k];
        int ny = j + dy[k];
        if(nx < 0 || nx >= n || ny < 0 || ny >= m || in[nx][ny] == '#')
          continue;
        if(cost[i][j] + 1 != cost[nx][ny]) continue;
        int inidxk = (nx*m+ny)*2;
        int outidxk = inidxk + 1;
        fg.add_edge(outidx,inidxk,1);
      }
    }
  }
  
  int fl = fg.max_flow(source,target) ;
  
  if(fl < 2){
    cout << "NA" << endl;
    return 0;
  }

  
  fg.dfsfill(source,target);
  rep(i,n) cout << in[i] << endl;
}

Submission Info

Judge Result