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
Submission Time |
|
Task |
D - Maze |
User |
yosupo |
Language |
C++11 (GCC 4.8.1) |
Score |
100 |
Code Size |
4775 Byte |
Status |
AC |
Exec Time |
34 ms |
Memory |
1440 KB |
Judge Result
Set Name |
all |
Score / Max Score |
100 / 100 |
Status |
|
Set Name |
Test Cases |
all |
manual_j1.txt, manual_j10.txt, manual_j11.txt, manual_j12.txt, manual_j13.txt, manual_j14.txt, manual_j15.txt, manual_j2.txt, manual_j3.txt, manual_j4.txt, manual_j5.txt, manual_j6.txt, manual_j7.txt, manual_j8.txt, manual_j9.txt, manual_k1.txt, manual_k2.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_max_01.txt, random_max_02.txt, random_max_03.txt, random_max_04.txt, random_max_05.txt, random_max_06.txt, random_max_07.txt, random_max_08.txt, random_max_09.txt, random_max_10.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, white_01.txt, white_02.txt, white_03.txt, white_04.txt |
Case Name |
Status |
Exec Time |
Memory |
manual_j1.txt |
AC |
26 ms |
1052 KB |
manual_j10.txt |
AC |
26 ms |
1176 KB |
manual_j11.txt |
AC |
29 ms |
1428 KB |
manual_j12.txt |
AC |
28 ms |
1048 KB |
manual_j13.txt |
AC |
26 ms |
1172 KB |
manual_j14.txt |
AC |
25 ms |
1048 KB |
manual_j15.txt |
AC |
27 ms |
1176 KB |
manual_j2.txt |
AC |
29 ms |
1188 KB |
manual_j3.txt |
AC |
26 ms |
1048 KB |
manual_j4.txt |
AC |
26 ms |
1056 KB |
manual_j5.txt |
AC |
25 ms |
924 KB |
manual_j6.txt |
AC |
26 ms |
1044 KB |
manual_j7.txt |
AC |
26 ms |
1052 KB |
manual_j8.txt |
AC |
25 ms |
936 KB |
manual_j9.txt |
AC |
26 ms |
932 KB |
manual_k1.txt |
AC |
28 ms |
1432 KB |
manual_k2.txt |
AC |
28 ms |
1316 KB |
random_01.txt |
AC |
27 ms |
1304 KB |
random_02.txt |
AC |
27 ms |
1184 KB |
random_03.txt |
AC |
26 ms |
1196 KB |
random_04.txt |
AC |
27 ms |
1308 KB |
random_05.txt |
AC |
28 ms |
1188 KB |
random_06.txt |
AC |
26 ms |
1052 KB |
random_max_01.txt |
AC |
34 ms |
1304 KB |
random_max_02.txt |
AC |
30 ms |
1240 KB |
random_max_03.txt |
AC |
30 ms |
1252 KB |
random_max_04.txt |
AC |
30 ms |
1440 KB |
random_max_05.txt |
AC |
32 ms |
1308 KB |
random_max_06.txt |
AC |
31 ms |
1176 KB |
random_max_07.txt |
AC |
31 ms |
1184 KB |
random_max_08.txt |
AC |
32 ms |
1184 KB |
random_max_09.txt |
AC |
28 ms |
1236 KB |
random_max_10.txt |
AC |
29 ms |
1180 KB |
sample_01.txt |
AC |
27 ms |
932 KB |
sample_02.txt |
AC |
26 ms |
932 KB |
sample_03.txt |
AC |
30 ms |
928 KB |
sample_04.txt |
AC |
25 ms |
932 KB |
white_01.txt |
AC |
29 ms |
1320 KB |
white_02.txt |
AC |
29 ms |
1316 KB |
white_03.txt |
AC |
32 ms |
1312 KB |
white_04.txt |
AC |
28 ms |
1312 KB |