#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <queue>
#include <cstring>
using namespace std;
/********************************************/
#define N 18000
#define inf 2000000000
#define Min(a,b) (((a)<(b))?a:b)
struct edge {
int s, t, f, v, next;
} e[10 * N];
int eid;
int node[N];
void init() {
memset(node, -1, sizeof(node));
eid = 0;
}
void addedge(int s, int t, int f, int v) {
e[eid].s = s;
e[eid].t = t;
e[eid].f = f;
e[eid].v = v;
e[eid].next = node[s];
node[s] = eid++;
e[eid].s = t;
e[eid].t = s;
e[eid].f = 0;
e[eid].v = -v;
e[eid].next = node[t];
node[t] = eid++;
}
int dist[N], path[N];
bool in[N];
queue<int> q;
int SPFA(int s, int t, int n) {
int i, u, v;
memset(in, false, sizeof(in));
for (i = 0; i < n; ++i)
dist[i] = inf;
dist[s] = 0;
path[s] = -1;
q.push(s);
in[s] = true;
while (!q.empty()) {
u = q.front();
q.pop();
in[u] = false;
for (i = node[u]; i != -1; i = e[i].next) {
v = e[i].t;
if (e[i].f > 0 && dist[u] + e[i].v < dist[v]) {
dist[v] = dist[u] + e[i].v;
path[v] = i;
if (!in[v]) {
q.push(v);
in[v] = true;
}
}
}
}
return dist[t] != inf;
}
void output() {
int i;
for (i = 0; i < eid; ++i)
printf("s:%d t:%d f:%d v:%d next:%d\n", e[i].s, e[i].t, e[i].f, e[i].v,
e[i].next);
}
int max_flow_min_cost(int s, int t, int n, int& cost) {
int i, minf, f = 0;
//output();
while (SPFA(s, t, n)) {
//printf("ok\n");
for (i = path[t], minf = e[path[t]].f; i != -1; i = path[e[i].s]) {
minf = Min(minf, e[i].f);
}
f += minf;
for (i = path[t]; i != -1; i = path[e[i].s]) {
cost += minf * e[i].v;
e[i].f -= minf;
e[i ^ 1].f += minf;
}
}
return f;
}
/********************************************/
char s[55][55];
int dir[4][2] = { 0, 1, 1, 0, 0, -1, -1, 0 };
vector<int> nt[10005];
int main() {
int n, m;
int i, j, k;
int S, T;
scanf("%d%d", &n, &m);
for (i = 0; i < n; ++i) {
scanf("%s", s[i]);
}
int start, end1, end2;
for (i = 0; i < n; ++i) {
for (j = 0; j < m; ++j) {
if (s[i][j] == 'S')
start = i * m + j;
if (s[i][j] == 'A')
end1 = i * m + j;
if (s[i][j] == 'B')
end2 = i * m + j;
}
}
////////////////1/////////////////////////
init();
for (i = 0; i < n; ++i) {
for (j = 0; j < m; ++j) {
if (s[i][j] == '#')
continue;
for (k = 0; k < 4; ++k) {
int ii, jj;
ii = i + dir[k][0];
jj = j + dir[k][1];
if (ii < 0 || jj < 0 || ii >= n || jj >= m)
continue;
if (s[ii][jj] == '#')
continue;
addedge(i * m + j, ii * m + jj, 1, 1);
}
}
}
S = n * m;
T = S + 1;
addedge(S, start, 2, 0);
addedge(end1, T, 1, 0);
int cost1;
cost1 = 0;
max_flow_min_cost(S, T, T + 1, cost1);
///////////////////////2//////////////////////////
init();
for (i = 0; i < n; ++i) {
for (j = 0; j < m; ++j) {
if (s[i][j] == '#')
continue;
for (k = 0; k < 4; ++k) {
int ii, jj;
ii = i + dir[k][0];
jj = j + dir[k][1];
if (ii < 0 || jj < 0 || ii >= n || jj >= m)
continue;
if (s[ii][jj] == '#')
continue;
addedge(i * m + j, ii * m + jj, 1, 1);
}
}
}
S = n * m;
T = S + 1;
addedge(S, start, 2, 0);
addedge(end2, T, 1, 0);
int cost2;
cost2 = 0;
max_flow_min_cost(S, T, T + 1, cost2);
///////////////////////3////////////////////////
init();
for (i = 0; i < n; ++i) {
for (j = 0; j < m; ++j) {
if (s[i][j] == '#')
continue;
addedge(i * m + j, n * m + i * m + j, 1, 0);
}
}
addedge(start, n * m + start, 1, 0);
for (i = 0; i < n; ++i) {
for (j = 0; j < m; ++j) {
if (s[i][j] == '#')
continue;
for (k = 0; k < 4; ++k) {
int ii, jj;
ii = i + dir[k][0];
jj = j + dir[k][1];
if (ii < 0 || jj < 0 || ii >= n || jj >= m)
continue;
if (s[ii][jj] == '#')
continue;
addedge(n * m + i * m + j, ii * m + jj, 1, 1);
}
}
}
S = 2 * n * m;
T = S + 1;
addedge(S, start, 2, 0);
addedge(n * m + end1, T, 1, 0);
addedge(n * m + end2, T, 1, 0);
int cost, f;
cost = 0;
f = 0;
f = max_flow_min_cost(S, T, T + 1, cost);
///////////////////////////////////////////////////////
if (f != 2) {
printf("NA\n");
return 0;
}
if (cost != cost1 + cost2) {
printf("NA\n");
return 0;
}
for (i = 0; i < eid; i += 2) {
if (e[i].f != 0)
continue;
if (e[i].s != S && e[i].t != T) {
if (e[i].s % (n * m) == e[i].t % (n * m))
continue;
nt[e[i].t % (n * m)].push_back(e[i].s % (n * m));
}
}
int now = nt[end1][0];
while (now != start) {
s[now / m][now % m] = 'a';
now = nt[now][0];
}
now = nt[end2][0];
while (now != start) {
s[now / m][now % m] = 'b';
now = nt[now][0];
}
for (i = 0; i < n; ++i) {
printf("%s\n", s[i]);
}
return 0;
}
./Main.cpp: In function ‘int main()’:
./Main.cpp:113:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:115:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]