Submission #306079

---

Source Code Expand

#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(),(x).rend()
#define sz(x) ((int)(x).size())
#define REP(i,b,n) for(int i=(int)(b);i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define repsz(i,v) rep(i,sz(v))
#define eb emplace_back
#define mt make_tuple
#define aur auto&
#define bit(n) (1LL<<(n))
using namespace std;
typedef long long ll;
//#define int long long
static const int INF = 1<<25;
static const double EPS = 1e-5;
template<class T>bool chmin(T&a,const T&b){if(a<=b)return false;a=b;return true;}
template<class T>bool chmax(T&a,const T&b){if(a>=b)return false;a=b;return true;}

// 無向の場合は頂点を倍にする.
typedef int Flow;
typedef int Cost;
struct E{ //{{{
    int src, dst;
    Flow capacity, flow;
    Cost cost;
    int rev;
    E(int s, int d, Flow cap, Cost cos, int r):
        src(s), dst(d), rev(r), capacity(cap), flow(0), cost(cos){}
}; //}}}
typedef vector<E> V;
typedef vector<V> G;
void add_edge(G &g, int src, int dst, Flow f, Cost c){ //{{{
    int i = sz(g[src]), j = sz(g[dst]);
    g[src].eb(src, dst, f, c, j);
    g[dst].eb(dst, src, 0,-c, i);
} //}}}
#define RESIDUE(e) (e.capacity - e.flow)
#define RCOST(e) (e.cost + h[e.src] - h[e.dst])
pair<Flow, Cost> primal_dual(G &g, int src, int dst){ //{{{
    int N = sz(g);
    pair<Flow, Cost> res;
    vector<Cost> h(N), dist(N);
    vector<pair<int, int> > parent(N);

    for(Flow F=INF; F>0;){
        dist.assign(N, INF); dist[src] = 0;
        parent.assign(N, make_pair(-1, -1));
        priority_queue<pair<Cost, int> > pq;
        for(pq.emplace(0, src); !pq.empty();){
            int i = pq.top().second;
            Cost c = -pq.top().first;
            pq.pop();
            if(dist[i] < c) continue;
            repsz(j, g[i]) if(RESIDUE(g[i][j]) > 0){
                E &e = g[i][j];
                Cost nc = c + RCOST(e);
                if(nc < dist[e.dst]){
                    dist[e.dst] = nc;
                    parent[e.dst] = make_pair(e.src, j);
                    pq.emplace(-nc, e.dst);
                }
            }
        }
        if(parent[dst].first == -1) break;
        Flow f = F;
        for(int i = dst; i != src; i = parent[i].first){
            E &e = g[parent[i].first][parent[i].second];
            chmin(f, RESIDUE(e));
        }
        for(int i = dst; i != src; i = parent[i].first){
            E &e = g[parent[i].first][parent[i].second];
            res.second += f * e.cost;
            e.flow += f;
            g[e.dst][e.rev].flow -= f;
        }
        F -= f;
        res.first += f;
        rep(i, N) h[i] += dist[i];
    }
    return res;
} //}}}


struct UnionFind{ //{{{
    vector<int> par;
    int n, cnt;
    UnionFind(int x=0){init(x);}
    void init(int x){
        cnt = n = x;
        par.assign(n, -1);
    }
    inline int find(int x){ return par[x] < 0 ? x : par[x] = find(par[x]); }
    inline bool same(int x, int y){ return find(x) == find(y); }
    inline bool unite(int x, int y){
        x = find(x); y = find(y);
        if(x == y) return false;
        --cnt;
        if(par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    inline int count(){ return cnt; }
    inline int count(int x){ return -par[find(x)]; }
};
//}}}

int dxy[] = {0, 1, 0, -1, 0};
bool solve(){//{{{
    int h, w;
    cin >> h >> w;
    vector<string> in(h);
    rep(i, h) cin >> in[i];
    int S, A, B;
    rep(i, h) rep(j, w){
        if(in[i][j] == 'S'){
            S = i * w + j;
        }else if(in[i][j] == 'A'){
            A = i * w + j;
        }else if(in[i][j] == 'B'){
            B = i * w + j;
        }else continue;
        in[i][j] = '.';
    }
    const int T = h*w*2;
    G g(h*w*2+1);
    rep(i, h*w) add_edge(g, i, i+h*w, 1, 0);
    rep(i, h) rep(j, w) rep(dir, 4){
        int ii = i + dxy[dir], jj = j + dxy[dir+1];
        if(!(0 <= ii and ii < h and 0 <= jj and jj < w)) continue;
        if(in[i][j] != '.' or in[ii][jj] != '.') continue;
        add_edge(g, h*w + i*w+j, ii*w+jj, 1, 1);
    }
    G cpA = g, cpB = g;
    add_edge(g, A+h*w, T, 1, 0);
    add_edge(cpA, A+h*w, T, 1, 0);
    add_edge(g, B+h*w, T, 1, 0);
    add_edge(cpB, B+h*w, T, 1, 0);
    auto tmp = primal_dual(g, S+h*w, T);
    if(tmp.first != 2){
        cout << "NA" << endl;
        return true;
    }
    auto tmpA = primal_dual(cpA, S+h*w, T);
    auto tmpB = primal_dual(cpB, S+h*w, T);
    if(tmp.second != tmpA.second + tmpB.second){
        cout << "NA" << endl;
        return true;
    }
//}}}

    UnionFind uf(h*w);
    for(aur v : g) for(aur e : v) if(e.flow > 0){
        if(e.src%(h*w) == S or e.dst%(h*w) == S) continue;
        //if(e.src%(h*w) != e.dst%(h*w)) continue;
        if(e.dst == T) continue;
        uf.unite(e.src%(h*w), e.dst%(h*w));
    }
    rep(i, h) rep(j, w) if(uf.find(i*w+j) == uf.find(A)) in[i][j] = 'a';
    rep(i, h) rep(j, w) if(uf.find(i*w+j) == uf.find(B)) in[i][j] = 'b';
    in[A/w][A%w] = 'A';
    in[B/w][B%w] = 'B';
    in[S/w][S%w] = 'S';
    for(aur v : in) cout << v << endl;
    return true;
}
signed main(){
    //cin.tie(0);
    //ios_base::sync_with_stdio(0);
    cout.setf(ios::fixed); cout.precision(10);
    solve();
    return 0;
}
// vim:set foldmethod=marker commentstring=//%s:

Submission Info

Judge Result