Submission #595276

---

Source Code Expand

#include<queue>
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)
#define eprintf(s...) fprintf(stderr, s)

template<class T> inline void amin(T &a, const T &b) { if (b<a) a=b; }
template<class T> inline void amax(T &a, const T &b) { if (a<b) a=b; }

struct MinCostMaxFlow {
    typedef int Flow;
    typedef int Cost;
    static const Flow FLOW_INF = 1<<29;
    static const Cost COST_INF = 1<<29;
    struct Edge {
	int src, dst;
	Cost cst;
	Flow cap;
	int rev;
	bool operator<(const Edge&y) const {
	    return cst > y.cst;
	}
    };
    typedef vector<vector<Edge> > Graph;
    Graph G;
    MinCostMaxFlow(int N) : G(N) {}
    // directed
    void add_edge(int u, int v, Cost x, Flow f) {
	G[u].push_back((Edge){ u, v, x, f, (int)G[v].size() });
	G[v].push_back((Edge){ v, u, -x, 0, (int)G[u].size()-1 });
    }

    Flow flow;
    Cost cost;
    Flow solve(int s, int t, Flow limit = FLOW_INF) {
	flow = 0;
	cost = 0;
	vector<Cost>len, h(G.size(), 0);
	vector<int> prev, prev_num;
	while (limit > 0) {
	    priority_queue<Edge> Q;
	    Q.push((Edge){-2, s, 0, 0, 0});
	    len.assign(G.size(), COST_INF);
	    prev.assign(G.size(), -1); prev_num.assign(G.size(), -1);
	    len[s] = 0;
	    while (!Q.empty()) {
		Edge e = Q.top(); Q.pop();
		for (int i=0; i<(int)G[e.dst].size(); i++) {
		    const Edge &f = G[e.dst][i];
		    if (f.cap > 0 && len[f.dst] > len[f.src] + f.cst + h[f.src] - h[f.dst]) {
			len[f.dst] = len[f.src] + f.cst + h[f.src] - h[f.dst];
			Q.push((Edge){ f.src, f.dst, len[f.dst], 0, 0 });
			prev[f.dst] = f.src; prev_num[f.dst] = i;
		    }
		}
	    }
	    if (prev[t] == -1) return flow;
	    for (int i=0; i<(int)G.size(); i++) h[i] += len[i];
	    
	    Flow f = limit;
	    for (int v=t; v!=s; v=prev[v])
		f = min(f, G[prev[v]][prev_num[v]].cap);
	    for (int v=t; v!=s; v=prev[v]) {
		Edge &e = G[prev[v]][prev_num[v]];
		e.cap -= f;
		G[e.dst][e.rev].cap += f;
	    }
	    limit -= f;
	    flow += f;
	    cost += f * h[t];
	}
	return flow;
    }
};
const MinCostMaxFlow::Flow MinCostMaxFlow::FLOW_INF;
const MinCostMaxFlow::Cost MinCostMaxFlow::COST_INF;


const int dy[] = {0, 1, 0, -1};
const int dx[] = {1, 0, -1, 0};

int H, W;
char F[99][99];
int D[2][99][99];
bool B[2][99][99];

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

int bfs(char g, int k) {
    memset(D[k], 0x3f, sizeof D[k]);
    queue<int> Y, X;
    REP (i, H) REP (j, W) if (F[i][j] == 'S') {
	Y.push(i);
	X.push(j);
	D[k][i][j] = 0;
    }

    while (Y.size()) {
	int y = Y.front(); Y.pop();
	int x = X.front(); X.pop();
	REP (d, 4) {
	    int yy = y + dy[d];
	    int xx = x + dx[d];
	    if (in(yy, xx) && D[k][yy][xx] > D[k][y][x] + 1 && F[yy][xx] != '#') {
		D[k][yy][xx] = D[k][y][x] + 1;
		Y.push(yy);
		X.push(xx);
	    }
	}
    }

    REP (i, H) REP (j, W) if (F[i][j] == g) {
	return D[k][i][j];
    }
}

int get(int r, int c, int l) {
    return r * W + c + l * H*W;
}
int main() {
    scanf("%d%d", &H, &W);
    REP (i, H) scanf("%s", F[i]);

    memset(D, 0x3f, sizeof D);
    int lenA = bfs('A', 0);
    int lenB = bfs('B', 1);
    
    if (lenA == D[0][98][98] || lenB == D[0][98][98]) {
	puts("NA");
	return 0;
    }

    int SRC = H*W * 2, SNK = SRC +1;
    MinCostMaxFlow X(SNK+1);
    REP (i, H) REP (j, W) {
	if (F[i][j] == '#') continue;
	if (i && F[i-1][j] != '#') {
	    X.add_edge(get(i-1, j, 1), get(i, j, 0), 1, 1);
	    X.add_edge(get(i, j, 1), get(i-1, j, 0), 1, 1);
	}
	if (j && F[i][j-1] != '#') {
	    X.add_edge(get(i, j-1, 1), get(i, j, 0), 1, 1);
	    X.add_edge(get(i, j, 1), get(i, j-1, 0), 1, 1);
	}

	if (F[i][j] == 'S') {
	    X.add_edge(SRC, get(i, j, 0), 0, 2);
	    X.add_edge(get(i, j, 0), get(i, j, 1), 0, 2);
	}else {
	    X.add_edge(get(i, j, 0), get(i, j, 1), 0, 1);
	}

	if (F[i][j] == 'A' || F[i][j] == 'B') X.add_edge(get(i, j, 1), SNK, 0, 2);
    }

    X.solve(SRC, SNK);
//    eprintf("%d %d\n", X.flow, X.cost);
    if (X.flow == 2 && X.cost == lenA + lenB) {
	char C[] = "AB";
	char s[] = "ab";
	REP (t, 2) {
	    REP (i, H) REP (j, W) {
		if (F[i][j] == C[t]) {
		    int v = get(i, j, 0);
		    while (v != SRC) {
			EACH (e, X.G[v]) {
			    if (e->cst <= 0 && e->cap >= 1) {
				v = e->dst;
				break;
			    }
			}
			if (v < H*W) {
			    int r = v / W, c = v % W;
			    if (F[r][c] == '.') F[r][c] = s[t];
			    if (F[r][c] == 'S') break;
			}
		    }
		}
	    }
	}

	REP (i, H) puts(F[i]);
    } else {
	puts("NA");
    }

    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:133:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:134:33: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]

Judge Result