Submission #307215
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
const int INF = 1<<28;
struct Edge {
int to, cost, cap, rev, rflag;
Edge(int to, int cost, int cap, int rev, int rflag)
: to(to), cost(cost), cap(cap), rev(rev), rflag(rflag) {}
Edge() {}
};
typedef vector<vector<Edge> > Graph;
const int MAXH = 55;
const int MAXW = 55;
const int di[] = {0,1,0,-1};
const int dj[] = {1,0,-1,0};
int H, W;
char G[MAXH][MAXW];
void addEdgeF(int from, int to, int cost, int cap, Graph &g) {
g[from].push_back(Edge(to,cost,cap,g[to].size(),0));
g[to].push_back(Edge(from,-cost,0,(int)g[from].size()-1,1));
}
int dfsF(int v, int t, int f, bool *used, Graph &g) {
if(v == t) return f;
used[v] = true;
for(int i = 0; i < g[v].size(); ++i) {
Edge &e = g[v][i];
if(!used[e.to] && e.cap > 0) {
int d = dfsF(e.to, t, min(f, e.cap), used, g);
if(d > 0) {
e.cap -= d;
g[e.to][e.rev].cap += d;
return d;
}
}
}
return 0;
}
int maxFlow(int s, int t, Graph g) {
int flow = 0;
bool *used = new bool[g.size()];
while(1) {
fill(used, used + g.size(), false);
int f = dfsF(s, t, INF, used, g);
if(f == 0) break;
flow += f;
}
delete [] used;
return flow;
}
typedef pair<int,int> Pair;
// O(FV^2)
int minCostFlow(int s, int t, int f, Graph &g) {
int V = g.size();
vector<int> h(V), dist(V), prevv(V), preve(V);
int res = 0;
fill(h.begin(), h.end(), 0);
while(f > 0) {
priority_queue<Pair, vector<Pair>, greater<Pair> > que;
fill(dist.begin(), dist.end(), INF);
dist[s] = 0;
que.push(Pair(0, s));
while(!que.empty()) {
Pair p = que.top(); que.pop();
int v = p.second;
if(dist[v] < p.first) continue;
for(int i = 0; i < g[v].size(); ++i) {
Edge &e = g[v][i];
int tmp = dist[v] + e.cost + h[v] - h[e.to];
if(e.cap > 0 && dist[e.to] > tmp) {
dist[e.to] = tmp;
prevv[e.to] = v;
preve[e.to] = i;
que.push(Pair(dist[e.to], e.to));
}
}
}
if(dist[t] == INF) {
return -1;
}
for(int v = 0; v < V; ++v) h[v] += dist[v];
int d = f;
for(int v = t; v != s; v = prevv[v]) {
d = min(d, g[prevv[v]][preve[v]].cap);
}
f -= d;
res += d * h[t];
for(int v = t; v != s; v = prevv[v]) {
Edge &e = g[prevv[v]][preve[v]];
e.cap -= d;
g[v][e.rev].cap += d;
}
}
return res;
}
int bfs(int si, int sj, int gi, int gj) {
vector<vector<int> > cost(H, vector<int>(W, INF));
queue<pair<int,int> > que;
que.push(make_pair(si, sj));
cost[si][sj] = 0;
while(que.size()) {
int pi = que.front().first;
int pj = que.front().second;
que.pop();
for(int k = 0; k < 4; ++k) {
int ni = pi + di[k];
int nj = pj + dj[k];
if(ni < 0 || ni >= H) continue;
if(nj < 0 || nj >= W) continue;
if(G[ni][nj] == '#')continue;
if(cost[ni][nj] != INF) continue;
que.push(make_pair(ni, nj));
cost[ni][nj] = cost[pi][pj] + 1;
if(ni == gi && nj == gj) return cost[ni][nj];
}
}
return INF;
}
void dfs(int v, char c, Graph &g) {
if(v < H*W) {
int i = v/W, j = v%W;
if(G[i][j] == '.') G[i][j] = c;
}
for(int i = 0; i < g[v].size(); ++i) {
const Edge &e = g[v][i];
if(e.rflag && e.cap) {
dfs(e.to, c, g);
break;
}
}
}
int main() {
cin >> H >> W;
int ai, aj, bi, bj, si, sj;
for(int i = 0; i < H; ++i) {
for(int j = 0; j < W; ++j) {
cin >> G[i][j];
if(G[i][j] == 'A') {
ai = i; aj = j;
}
if(G[i][j] == 'B') {
bi = i; bj = j;
}
if(G[i][j] == 'S') {
si = i; sj = j;
}
}
}
int costA = bfs(si, sj, ai, aj);
int costB = bfs(si, sj, bi, bj);
//void addEdgeF(int from, int to, int cost, int cap, Graph &g) {
Graph g(H*W*2+1);
int src = H*W+si*W+sj;
int dst = H*W*2;
for(int i = 0; i < H*W; ++i) {
if(G[i/W][i%W] != '#')
addEdgeF(i, H*W+i, 0, 1, g);
}
addEdgeF(H*W + ai*W+aj, dst, 0, 1, g);
addEdgeF(H*W + bi*W+bj, dst, 0, 1, g);
for(int i = 0; i < H; ++i) {
for(int j = 0; j < W; ++j) {
int from = H*W+i * W + j;
for(int k = 0; k < 4; ++k) {
int ni = i + di[k];
int nj = j + dj[k];
if(ni < 0 || ni >= H) continue;
if(nj < 0 || nj >= W) continue;
int to = ni * W + nj;
addEdgeF(from, to, 1, 1, g);
}
}
}
int sum = minCostFlow(src, dst, 2, g);
if(sum != costA + costB) {
cout << "NA" << endl;
} else {
dfs(ai*W+aj, 'a', g);
dfs(bi*W+bj, 'b', g);
for(int i = 0; i < H; ++i) {
for(int j = 0; j < W; ++j) {
cout << G[i][j];
}
cout << endl;
}
}
return 0;
}
Submission Info
Submission Time |
|
Task |
D - Maze |
User |
zukky |
Language |
C++ (G++ 4.6.4) |
Score |
100 |
Code Size |
4936 Byte |
Status |
AC |
Exec Time |
32 ms |
Memory |
1948 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 |
24 ms |
924 KB |
manual_j10.txt |
AC |
22 ms |
928 KB |
manual_j11.txt |
AC |
32 ms |
1824 KB |
manual_j12.txt |
AC |
24 ms |
928 KB |
manual_j13.txt |
AC |
24 ms |
816 KB |
manual_j14.txt |
AC |
24 ms |
928 KB |
manual_j15.txt |
AC |
23 ms |
924 KB |
manual_j2.txt |
AC |
29 ms |
1636 KB |
manual_j3.txt |
AC |
24 ms |
932 KB |
manual_j4.txt |
AC |
24 ms |
928 KB |
manual_j5.txt |
AC |
22 ms |
928 KB |
manual_j6.txt |
AC |
22 ms |
804 KB |
manual_j7.txt |
AC |
23 ms |
672 KB |
manual_j8.txt |
AC |
22 ms |
800 KB |
manual_j9.txt |
AC |
22 ms |
928 KB |
manual_k1.txt |
AC |
29 ms |
1948 KB |
manual_k2.txt |
AC |
30 ms |
1864 KB |
random_01.txt |
AC |
27 ms |
1700 KB |
random_02.txt |
AC |
31 ms |
1816 KB |
random_03.txt |
AC |
29 ms |
1684 KB |
random_04.txt |
AC |
29 ms |
1808 KB |
random_05.txt |
AC |
29 ms |
1304 KB |
random_06.txt |
AC |
26 ms |
1428 KB |
random_max_01.txt |
AC |
29 ms |
1824 KB |
random_max_02.txt |
AC |
28 ms |
1820 KB |
random_max_03.txt |
AC |
32 ms |
1708 KB |
random_max_04.txt |
AC |
32 ms |
1740 KB |
random_max_05.txt |
AC |
30 ms |
1816 KB |
random_max_06.txt |
AC |
29 ms |
1692 KB |
random_max_07.txt |
AC |
30 ms |
1696 KB |
random_max_08.txt |
AC |
31 ms |
1752 KB |
random_max_09.txt |
AC |
31 ms |
1696 KB |
random_max_10.txt |
AC |
30 ms |
1692 KB |
sample_01.txt |
AC |
24 ms |
804 KB |
sample_02.txt |
AC |
24 ms |
800 KB |
sample_03.txt |
AC |
25 ms |
792 KB |
sample_04.txt |
AC |
25 ms |
924 KB |
white_01.txt |
AC |
32 ms |
1828 KB |
white_02.txt |
AC |
32 ms |
1820 KB |
white_03.txt |
AC |
30 ms |
1832 KB |
white_04.txt |
AC |
29 ms |
1820 KB |