Submission #306143
Source Code Expand
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_DEPRECATE
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <cassert>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <list>
#include <iomanip>
#include <fstream>
#include <iterator>
#include <bitset>
using namespace std;
typedef long long ll;
typedef pair<int, int> Pii;
typedef pair<ll, ll> Pll;
#define FOR(i,n) for(int i = 0; i < (n); i++)
#define sz(c) ((int)(c).size())
#define ten(x) ((int)1e##x)
template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
typedef unsigned long long ull;
struct Edge {
int cap; // capacity
int to;
int rev; // reverse edge id
Edge() {}
Edge(int c, int t, int r) :
cap(c), to(t), rev(r) {
}
};
struct CostEdge : public Edge {
int cost;
CostEdge() : Edge() {}
CostEdge(int c, int t, int cs, int r) :
Edge(c, t, r), cost(cs) {
}
};
template<class E> // Edge type
class Graph {
public:
typedef std::vector<std::vector<E> > G;
private:
G g;
public:
Graph(int n) : g(G(n)) {}
void addEdge(int from, int to, int cap, int cost) {
g[from].push_back(E(cap, to, cost, g[to].size()));
g[to].push_back(E(0, from, -cost, g[from].size() - 1)); //rev edge
}
G &getRowGraph() {
return g;
}
};
// O(VE+FElogV)
template<class E>
int minCostFlow(Graph<E> &graph, int s, int t, int f, bool negative = false) {
typedef pair<int, int> P;
typename Graph<E>::G &g = graph.getRowGraph();
int n = g.size();
int res = 0;
vector<int> h(n, 0);
vector<int> prevv(n);
vector<int> preve(n);
const int inf = 10000000; //check
//負の辺に対応?
if (negative) {
vector<int> dist(n, inf);
dist[s] = 0;
bool update = true;
while (update) {
update = false;
for (int v = 0; v < n; v++) {
if (dist[v] == inf) continue;
for (int i = 0; i < (int)g[v].size(); i++) {
E &e = g[v][i];
if (e.cap > 0 && dist[e.to] > dist[v] + e.cost) {
dist[e.to] = dist[v] + e.cost;
prevv[e.to] = v;
preve[e.to] = i;
update = true;
}
}
}
}
for (int i = 0; i < n; i++)
h[i] = dist[i];
}
while (f > 0) {
//ダイクストラで最短経路(cost = 辺の費用)
priority_queue<P, vector<P>, greater<P> > que;
vector<int> dist(n, inf);
dist[s] = 0;
que.push(P(0, s));
while (!que.empty()) {
P p = que.top(); que.pop();
int v = p.second;
if (dist[v] < p.first) continue;
for (int i = 0; i < (int)g[v].size(); i++) {
E &e = g[v][i];
if (e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]) {
dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
prevv[e.to] = v;
preve[e.to] = i;
que.push(P(dist[e.to], e.to));
}
}
}
if (dist[t] == inf) {
return -1; //最短経路なし
}
for (int v = 0; v < n; v++) h[v] += dist[v];
//s-t間に目一杯流す
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]) {
E &e = g[prevv[v]][preve[v]];
e.cap -= d;
g[v][e.rev].cap += d;
}
}
return res;
}
#define ID(a,b) (a*w+b)
char board[50][51];
int main(){
int h, w; cin >> h >> w;
FOR(i, h) cin >> board[i];
const int n = 2 + 2 * h*w;
int a, b, s;
FOR(i, h) FOR(j, w) {
if (board[i][j] == 'A') a = ID(i, j);
if (board[i][j] == 'B') b = ID(i, j);
if (board[i][j] == 'S') s = ID(i, j);
}
Graph<CostEdge> g(n);
FOR(i, h) FOR(j, w) {
if (board[i][j] == '#') continue;
const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { 1, 0, -1, 0 };
int id = ID(i, j);
FOR(k, 4) {
int ni = i + dx[k];
int nj = j + dy[k];
if (0 <= ni && ni < h && 0 <= nj && nj < w && board[ni][nj] != '#') {
int nid = ID(ni, nj);
g.addEdge(id * 2 + 1, nid * 2, 1,1);
}
}
}
FOR(i, h) FOR(j, w) {
if (board[i][j] == '#') continue;
int id = ID(i, j);
int cap = (id == s) ? 2 : 1;
g.addEdge(id * 2, id * 2 + 1 , cap, 0);
}
const int src = n - 2, dst = n - 1;
g.addEdge(src, s * 2, 2, 0);
auto g2 = g;
g2.addEdge(a * 2 + 1, dst, 1 , 0);
int s2a = minCostFlow(g2, src, dst, 1);
auto g3 = g;
g3.addEdge(b * 2 + 1, dst, 1 , 0);
int s2b = minCostFlow(g3, src, dst, 1);
g.addEdge(a * 2 + 1, dst, 1, 0);
g.addEdge(b * 2 + 1, dst, 1, 0);
int s2ab = minCostFlow(g, src, dst, 2);
if (s2ab != s2a + s2b) {
puts("NA");
} else {
{
int cur = 2 * a;
auto rG = g.getRowGraph();
while (cur != 2 * s) {
for (auto e : rG[cur]) {
if (e.cost == -1 && e.cap == 1) {
int from = e.to;
cur = from - 1;
int i = cur / 2 / w;
int j = cur / 2 % w;
board[i][j] = 'a';
//fprintf(stderr,"%d %d\n",i,j);
break;
}
}
}
}
{
int cur = 2 * b;
auto rG = g.getRowGraph();
while (cur != 2 * s) {
for (auto e : rG[cur]) {
if (e.cost == -1 && e.cap == 1) {
int from = e.to;
cur = from - 1;
int i = cur / 2 / w;
int j = cur / 2 % w;
//fprintf(stderr, "%d %d\n", i, j);
board[i][j] = 'b';
break;
}
}
}
}
board[s / w][s%w] = 'S';
FOR(i, h) puts(board[i]);
}
}
Submission Info
Submission Time |
|
Task |
D - Maze |
User |
math |
Language |
C++11 (GCC 4.8.1) |
Score |
100 |
Code Size |
5801 Byte |
Status |
AC |
Exec Time |
39 ms |
Memory |
3352 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 |
27 ms |
856 KB |
manual_j10.txt |
AC |
27 ms |
856 KB |
manual_j11.txt |
AC |
37 ms |
3348 KB |
manual_j12.txt |
AC |
24 ms |
928 KB |
manual_j13.txt |
AC |
25 ms |
964 KB |
manual_j14.txt |
AC |
24 ms |
924 KB |
manual_j15.txt |
AC |
26 ms |
1052 KB |
manual_j2.txt |
AC |
31 ms |
2140 KB |
manual_j3.txt |
AC |
23 ms |
924 KB |
manual_j4.txt |
AC |
30 ms |
836 KB |
manual_j5.txt |
AC |
26 ms |
852 KB |
manual_j6.txt |
AC |
28 ms |
864 KB |
manual_j7.txt |
AC |
25 ms |
860 KB |
manual_j8.txt |
AC |
25 ms |
924 KB |
manual_j9.txt |
AC |
25 ms |
928 KB |
manual_k1.txt |
AC |
37 ms |
3032 KB |
manual_k2.txt |
AC |
39 ms |
2648 KB |
random_01.txt |
AC |
34 ms |
2260 KB |
random_02.txt |
AC |
37 ms |
2396 KB |
random_03.txt |
AC |
32 ms |
2092 KB |
random_04.txt |
AC |
32 ms |
2136 KB |
random_05.txt |
AC |
33 ms |
1944 KB |
random_06.txt |
AC |
31 ms |
1624 KB |
random_max_01.txt |
AC |
38 ms |
3344 KB |
random_max_02.txt |
AC |
38 ms |
3164 KB |
random_max_03.txt |
AC |
34 ms |
2648 KB |
random_max_04.txt |
AC |
38 ms |
2984 KB |
random_max_05.txt |
AC |
39 ms |
2824 KB |
random_max_06.txt |
AC |
35 ms |
2648 KB |
random_max_07.txt |
AC |
35 ms |
2524 KB |
random_max_08.txt |
AC |
32 ms |
2396 KB |
random_max_09.txt |
AC |
30 ms |
2012 KB |
random_max_10.txt |
AC |
29 ms |
2008 KB |
sample_01.txt |
AC |
26 ms |
856 KB |
sample_02.txt |
AC |
23 ms |
924 KB |
sample_03.txt |
AC |
24 ms |
856 KB |
sample_04.txt |
AC |
27 ms |
856 KB |
white_01.txt |
AC |
39 ms |
3352 KB |
white_02.txt |
AC |
37 ms |
3352 KB |
white_03.txt |
AC |
39 ms |
3348 KB |
white_04.txt |
AC |
35 ms |
2904 KB |