Submission #306151

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <complex>
#include <set>
#include <vector>
#include <stack>
#include <tuple>
#include <algorithm>
#include <cassert>
#include <cstring>
#include <queue>
#include <string>
#include <map>

using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;

template<int V>
struct MaxFlow {
    using T = int;
    const T INF = 1<<28;
    struct Edge {
        int to, rev;
        T cap;
    };
    vector<Edge> g[V];
    int level[V];
    int iter[V];

    void add(int from, int to, T cap) {
        g[from].push_back(Edge{to, (int)g[to].size(), cap});
        g[to].push_back(Edge{from, (int)g[from].size()-1, 0});
    }

    void add_multi(int from, int to, T cap) {
        g[from].push_back(Edge{to, (int)g[to].size(), cap});
        g[to].push_back(Edge{from, (int)g[from].size()-1, cap});
    }

    void bfs(int s) {
        fill_n(level, V, -1);
        queue<int> que;
        level[s] = 0;
        que.push(s);
        while (!que.empty()) {
            int v = que.front(); que.pop();
            for (Edge e: g[v]) {
                if (e.cap <= 0) continue;
                if (level[e.to] < 0) {
                    level[e.to] = level[v] + 1;
                    que.push(e.to);
                }
            }
        }
    }

    T dfs(int v, int t, T f) {
        if (v == t) return f;
        for (int &i = iter[v]; i < g[v].size(); i++) {
            Edge &e = g[v][i];
            if (e.cap <= 0) continue;
            if (level[v] < level[e.to]) {
                T d = dfs(e.to, t, min(f, e.cap));
                if (d <= 0) continue;
                e.cap -= d;
                g[e.to][e.rev].cap += d;
                return d;
            }
        }
        return 0;
    }

    T exec(int s, int t) {
        T flow = 0;
        while (true) {
            bfs(s);
            if (level[t] < 0) return flow;
            fill_n(iter, V, 0);
            T f;
            while ((f = dfs(s, t, INF)) > 0) {
                flow += f;
            }
        }
    }
};

const int MN = 60;
const int MV = MN*MN;
const int INF = 1e7;
const int d4[4][2] = {
    {0, 1},
    {1, 0},
    {0, -1},
    {-1, 0},
};
P s, a, b;
int H, W;
int g[MN][MN];
string gs[MN];
int ms[MN][MN];
MaxFlow<MV*2 + 10> mf;

bool bc(int y, int x) {
    return (0 <= y && y < H && 0 <= x && x < W);
}


int main() {
    cin >> H >> W;
    for (int i = 0; i < H; i++) {
        string u;
        cin >> u;
        gs[i] = u;
        for (int j = 0; j < W; j++) {
            g[i][j] = (u[j] == '#');
            if (u[j] == 'S') {
                s = P(i, j);
            }
            if (u[j] == 'A') {
                a = P(i, j);
            }
            if (u[j] == 'B') {
                b = P(i, j);
            }
        }
    }

    memset(ms, -1, sizeof(ms));
    queue<T> q;
    q.push(T(s.first, s.second, 0));
    while (!q.empty()) {
        int y, x, d;
        tie(y, x, d) = q.front(); q.pop();
        if (ms[y][x] != -1) continue;
        ms[y][x] = d;
        for (int i = 0; i < 4; i++) {
            int yy = y+d4[i][1], xx = x+d4[i][0];
            if (yy < 0 || H <= yy || xx < 0 || W <= xx) continue;
            if (g[yy][xx]) continue;
            q.push(T(yy, xx, d+1));
        }
    }
    for (int y = 0; y < H; y++) {
        for (int x = 0; x < W; x++) {
            mf.add(y*MN+x, y*MN+x+MV, 1);
            for (int i = 0; i < 4; i++) {
                int ny = y+d4[i][1], nx = x+d4[i][0];
                if (!bc(ny, nx)) continue;
                if (ms[y][x] == -1) continue;
                if (ms[ny][nx] == -1) continue;
                if (ms[y][x] <= ms[ny][nx]) continue;
                mf.add(y*MN+x+MV, ny*MN+nx, 1);
            }
        }
    }
    int vs = MV*2;
    mf.add(vs, a.first*MN+a.second, 1);
    mf.add(vs, b.first*MN+b.second, 1);
    if (mf.exec(vs, s.first*MN+s.second) != 2) {
        cout << "NA" << endl;
        return 0;
    }
    int vv = a.first*MN+a.second+MV;
    while (true) {
        for (auto e: mf.g[vv]) {
            if (!e.cap) {
                vv = e.to+MV;
            }
        }
        if (vv-MV == s.first*MN+s.second) break;
        gs[(vv-MV)/MN][(vv-MV)%MN] = 'a';
    }
    vv = b.first*MN+b.second+MV;
    while (true) {
        for (auto e: mf.g[vv]) {
            if (!e.cap) {
                vv = e.to+MV;
            }
        }
        if (vv-MV == s.first*MN+s.second) break;
        gs[(vv-MV)/MN][(vv-MV)%MN] = 'b';
    }
    for (int i = 0; i < H; i++) {
        cout << gs[i] << endl;
    }
    return 0;
}

Submission Info

Judge Result