Submission #3058122
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
template< typename flow_t, typename cost_t >
struct PrimalDual {
const cost_t INF;
struct edge {
int to;
flow_t cap;
cost_t cost;
int rev;
bool isrev;
};
vector< vector< edge > > graph;
vector< cost_t > potential, min_cost;
vector< int > prevv, preve;
PrimalDual(int V) : graph(V), INF(numeric_limits< cost_t >::max()) {}
void add_edge(int from, int to, flow_t cap, cost_t cost) {
graph[from].emplace_back((edge) {to, cap, cost, (int) graph[to].size(), false});
graph[to].emplace_back((edge) {from, 0, -cost, (int) graph[from].size() - 1, true});
}
cost_t min_cost_flow(int s, int t, flow_t f) {
int V = (int) graph.size();
cost_t ret = 0;
using Pi = pair< cost_t, int >;
priority_queue< Pi, vector< Pi >, greater< Pi > > que;
potential.assign(V, 0);
preve.assign(V, -1);
prevv.assign(V, -1);
while(f > 0) {
min_cost.assign(V, INF);
que.emplace(0, s);
min_cost[s] = 0;
while(!que.empty()) {
Pi p = que.top();
que.pop();
if(min_cost[p.second] < p.first) continue;
for(int i = 0; i < graph[p.second].size(); i++) {
edge &e = graph[p.second][i];
cost_t nextCost = min_cost[p.second] + e.cost + potential[p.second] - potential[e.to];
if(e.cap > 0 && min_cost[e.to] > nextCost) {
min_cost[e.to] = nextCost;
prevv[e.to] = p.second, preve[e.to] = i;
que.emplace(min_cost[e.to], e.to);
}
}
}
if(min_cost[t] == INF) return -1;
for(int v = 0; v < V; v++) potential[v] += min_cost[v];
flow_t addflow = f;
for(int v = t; v != s; v = prevv[v]) {
addflow = min(addflow, graph[prevv[v]][preve[v]].cap);
}
f -= addflow;
ret += addflow * potential[t];
for(int v = t; v != s; v = prevv[v]) {
edge &e = graph[prevv[v]][preve[v]];
e.cap -= addflow;
graph[v][e.rev].cap += addflow;
}
}
return ret;
}
void output() {
for(int i = 0; i < graph.size(); i++) {
for(auto &e : graph[i]) {
if(e.isrev) continue;
auto &rev_e = graph[e.to][e.rev];
cout << i << "->" << e.to << " (flow: " << rev_e.cap << "/" << rev_e.cap + e.cap << ")" << endl;
}
}
}
};
int W, H;
char S[50][50];
int min_cost[50][50];
const int vx[] = {0, 1, 0, -1}, vy[] = {1, 0, -1, 0};
int bfs(int sx, int sy, char c) {
memset(min_cost, -1, sizeof(min_cost));
queue< pair< int, int > > que;
que.emplace(sx, sy);
min_cost[sx][sy] = 0;
while(!que.empty()) {
auto p = que.front();
que.pop();
if(S[p.second][p.first] == c) return (min_cost[p.first][p.second]);
for(int i = 0; i < 4; i++) {
int nx = p.first + vx[i], ny = p.second + vy[i];
if(nx < 0 || ny < 0 || nx >= W || ny >= H) continue;
if(min_cost[nx][ny] != -1) continue;
if(S[ny][nx] == '#') continue;
min_cost[nx][ny] = min_cost[p.first][p.second] + 1;
que.emplace(nx, ny);
}
}
return (-1);
}
int main() {
int SX, SY, GX[2], GY[2];
cin >> H >> W;
for(int i = 0; i < H; i++) {
cin >> S[i];
for(int j = 0; j < W; j++) {
if(S[i][j] == 'S') SX = j, SY = i;
else if(isalpha(S[i][j])) {
bool t = S[i][j] == 'B';
GX[t] = j, GY[t] = i;
}
}
}
bfs(SX, SY, -1);
if(min_cost[GX[0]][GY[0]] == -1 || min_cost[GX[1]][GY[1]] == -1) {
cout << "NA" << endl;
return 0;
}
PrimalDual< int, int > flow(H * W + 1);
for(int i = 0; i < H; i++) {
for(int j = 0; j < W; j++) {
for(int k = 0; k < 4; k++) {
int ny = i + vy[k], nx = j + vx[k];
if(ny < 0 || nx < 0 || ny >= H || nx >= W) continue;
if(min_cost[nx][ny] == -1 || min_cost[j][i] == -1) continue;
if(min_cost[j][i] + 1 == min_cost[nx][ny]) {
flow.add_edge(i * W + j, ny * W + nx, 1, 1);
}
}
}
}
flow.add_edge(GY[0] * W + GX[0], H * W, 1, 0);
flow.add_edge(GY[1] * W + GX[1], H * W, 1, 0);
if(flow.min_cost_flow(SY * W + SX, H * W, 2) == min_cost[GX[0]][GY[0]] + min_cost[GX[1]][GY[1]]) {
function< int(int) > dfs = [&](int idx) {
if(idx == GY[0] * W + GX[0]) {
return 1;
} else if(idx == GY[1] * W + GX[1]) {
return 2;
} else {
int type = 0;
for(auto &e : flow.graph[idx]) {
if(e.isrev) continue;
auto &rev_e = flow.graph[e.to][e.rev];
if(rev_e.cap == 1) {
type += dfs(e.to);
}
}
if(type == 1) S[idx / W][idx % W] = 'a';
else if(type == 2) S[idx / W][idx % W] = 'b';
return type;
}
};
dfs(SY * W + SX);
for(int i = 0; i < H; i++) cout << S[i] << endl;
} else {
cout << "NA" << endl;
}
}
Submission Info
Submission Time |
|
Task |
D - Maze |
User |
ei13333 |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
5026 Byte |
Status |
WA |
Exec Time |
2 ms |
Memory |
384 KB |
Judge Result
Set Name |
all |
Score / Max Score |
0 / 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 |
1 ms |
256 KB |
manual_j10.txt |
AC |
1 ms |
256 KB |
manual_j11.txt |
WA |
2 ms |
384 KB |
manual_j12.txt |
AC |
1 ms |
256 KB |
manual_j13.txt |
AC |
1 ms |
256 KB |
manual_j14.txt |
WA |
1 ms |
256 KB |
manual_j15.txt |
WA |
1 ms |
256 KB |
manual_j2.txt |
WA |
1 ms |
256 KB |
manual_j3.txt |
AC |
1 ms |
256 KB |
manual_j4.txt |
WA |
1 ms |
256 KB |
manual_j5.txt |
WA |
1 ms |
256 KB |
manual_j6.txt |
AC |
1 ms |
256 KB |
manual_j7.txt |
AC |
1 ms |
256 KB |
manual_j8.txt |
AC |
1 ms |
256 KB |
manual_j9.txt |
AC |
1 ms |
256 KB |
manual_k1.txt |
WA |
1 ms |
256 KB |
manual_k2.txt |
AC |
1 ms |
256 KB |
random_01.txt |
AC |
1 ms |
256 KB |
random_02.txt |
WA |
1 ms |
256 KB |
random_03.txt |
WA |
1 ms |
256 KB |
random_04.txt |
WA |
1 ms |
256 KB |
random_05.txt |
WA |
2 ms |
384 KB |
random_06.txt |
AC |
2 ms |
384 KB |
random_max_01.txt |
WA |
1 ms |
256 KB |
random_max_02.txt |
WA |
1 ms |
256 KB |
random_max_03.txt |
AC |
1 ms |
256 KB |
random_max_04.txt |
WA |
1 ms |
256 KB |
random_max_05.txt |
WA |
1 ms |
256 KB |
random_max_06.txt |
WA |
1 ms |
256 KB |
random_max_07.txt |
WA |
1 ms |
256 KB |
random_max_08.txt |
WA |
1 ms |
256 KB |
random_max_09.txt |
AC |
1 ms |
256 KB |
random_max_10.txt |
AC |
1 ms |
256 KB |
sample_01.txt |
AC |
1 ms |
256 KB |
sample_02.txt |
AC |
1 ms |
256 KB |
sample_03.txt |
AC |
1 ms |
256 KB |
sample_04.txt |
AC |
1 ms |
256 KB |
white_01.txt |
WA |
1 ms |
256 KB |
white_02.txt |
WA |
1 ms |
256 KB |
white_03.txt |
WA |
1 ms |
256 KB |
white_04.txt |
AC |
1 ms |
256 KB |