Submission #306079
Source Code Expand
#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(),(x).rend()
#define sz(x) ((int)(x).size())
#define REP(i,b,n) for(int i=(int)(b);i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define repsz(i,v) rep(i,sz(v))
#define eb emplace_back
#define mt make_tuple
#define aur auto&
#define bit(n) (1LL<<(n))
using namespace std;
typedef long long ll;
//#define int long long
static const int INF = 1<<25;
static const double EPS = 1e-5;
template<class T>bool chmin(T&a,const T&b){if(a<=b)return false;a=b;return true;}
template<class T>bool chmax(T&a,const T&b){if(a>=b)return false;a=b;return true;}
// 無向の場合は頂点を倍にする.
typedef int Flow;
typedef int Cost;
struct E{ //{{{
int src, dst;
Flow capacity, flow;
Cost cost;
int rev;
E(int s, int d, Flow cap, Cost cos, int r):
src(s), dst(d), rev(r), capacity(cap), flow(0), cost(cos){}
}; //}}}
typedef vector<E> V;
typedef vector<V> G;
void add_edge(G &g, int src, int dst, Flow f, Cost c){ //{{{
int i = sz(g[src]), j = sz(g[dst]);
g[src].eb(src, dst, f, c, j);
g[dst].eb(dst, src, 0,-c, i);
} //}}}
#define RESIDUE(e) (e.capacity - e.flow)
#define RCOST(e) (e.cost + h[e.src] - h[e.dst])
pair<Flow, Cost> primal_dual(G &g, int src, int dst){ //{{{
int N = sz(g);
pair<Flow, Cost> res;
vector<Cost> h(N), dist(N);
vector<pair<int, int> > parent(N);
for(Flow F=INF; F>0;){
dist.assign(N, INF); dist[src] = 0;
parent.assign(N, make_pair(-1, -1));
priority_queue<pair<Cost, int> > pq;
for(pq.emplace(0, src); !pq.empty();){
int i = pq.top().second;
Cost c = -pq.top().first;
pq.pop();
if(dist[i] < c) continue;
repsz(j, g[i]) if(RESIDUE(g[i][j]) > 0){
E &e = g[i][j];
Cost nc = c + RCOST(e);
if(nc < dist[e.dst]){
dist[e.dst] = nc;
parent[e.dst] = make_pair(e.src, j);
pq.emplace(-nc, e.dst);
}
}
}
if(parent[dst].first == -1) break;
Flow f = F;
for(int i = dst; i != src; i = parent[i].first){
E &e = g[parent[i].first][parent[i].second];
chmin(f, RESIDUE(e));
}
for(int i = dst; i != src; i = parent[i].first){
E &e = g[parent[i].first][parent[i].second];
res.second += f * e.cost;
e.flow += f;
g[e.dst][e.rev].flow -= f;
}
F -= f;
res.first += f;
rep(i, N) h[i] += dist[i];
}
return res;
} //}}}
struct UnionFind{ //{{{
vector<int> par;
int n, cnt;
UnionFind(int x=0){init(x);}
void init(int x){
cnt = n = x;
par.assign(n, -1);
}
inline int find(int x){ return par[x] < 0 ? x : par[x] = find(par[x]); }
inline bool same(int x, int y){ return find(x) == find(y); }
inline bool unite(int x, int y){
x = find(x); y = find(y);
if(x == y) return false;
--cnt;
if(par[x] > par[y]) swap(x, y);
par[x] += par[y];
par[y] = x;
return true;
}
inline int count(){ return cnt; }
inline int count(int x){ return -par[find(x)]; }
};
//}}}
int dxy[] = {0, 1, 0, -1, 0};
bool solve(){//{{{
int h, w;
cin >> h >> w;
vector<string> in(h);
rep(i, h) cin >> in[i];
int S, A, B;
rep(i, h) rep(j, w){
if(in[i][j] == 'S'){
S = i * w + j;
}else if(in[i][j] == 'A'){
A = i * w + j;
}else if(in[i][j] == 'B'){
B = i * w + j;
}else continue;
in[i][j] = '.';
}
const int T = h*w*2;
G g(h*w*2+1);
rep(i, h*w) add_edge(g, i, i+h*w, 1, 0);
rep(i, h) rep(j, w) rep(dir, 4){
int ii = i + dxy[dir], jj = j + dxy[dir+1];
if(!(0 <= ii and ii < h and 0 <= jj and jj < w)) continue;
if(in[i][j] != '.' or in[ii][jj] != '.') continue;
add_edge(g, h*w + i*w+j, ii*w+jj, 1, 1);
}
G cpA = g, cpB = g;
add_edge(g, A+h*w, T, 1, 0);
add_edge(cpA, A+h*w, T, 1, 0);
add_edge(g, B+h*w, T, 1, 0);
add_edge(cpB, B+h*w, T, 1, 0);
auto tmp = primal_dual(g, S+h*w, T);
if(tmp.first != 2){
cout << "NA" << endl;
return true;
}
auto tmpA = primal_dual(cpA, S+h*w, T);
auto tmpB = primal_dual(cpB, S+h*w, T);
if(tmp.second != tmpA.second + tmpB.second){
cout << "NA" << endl;
return true;
}
//}}}
UnionFind uf(h*w);
for(aur v : g) for(aur e : v) if(e.flow > 0){
if(e.src%(h*w) == S or e.dst%(h*w) == S) continue;
//if(e.src%(h*w) != e.dst%(h*w)) continue;
if(e.dst == T) continue;
uf.unite(e.src%(h*w), e.dst%(h*w));
}
rep(i, h) rep(j, w) if(uf.find(i*w+j) == uf.find(A)) in[i][j] = 'a';
rep(i, h) rep(j, w) if(uf.find(i*w+j) == uf.find(B)) in[i][j] = 'b';
in[A/w][A%w] = 'A';
in[B/w][B%w] = 'B';
in[S/w][S%w] = 'S';
for(aur v : in) cout << v << endl;
return true;
}
signed main(){
//cin.tie(0);
//ios_base::sync_with_stdio(0);
cout.setf(ios::fixed); cout.precision(10);
solve();
return 0;
}
// vim:set foldmethod=marker commentstring=//%s:
Submission Info
Submission Time |
|
Task |
D - Maze |
User |
MiSawa |
Language |
C++11 (GCC 4.8.1) |
Score |
100 |
Code Size |
5454 Byte |
Status |
AC |
Exec Time |
40 ms |
Memory |
3620 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 |
22 ms |
932 KB |
manual_j10.txt |
AC |
23 ms |
924 KB |
manual_j11.txt |
AC |
36 ms |
3496 KB |
manual_j12.txt |
AC |
23 ms |
796 KB |
manual_j13.txt |
AC |
22 ms |
804 KB |
manual_j14.txt |
AC |
24 ms |
920 KB |
manual_j15.txt |
AC |
30 ms |
928 KB |
manual_j2.txt |
AC |
29 ms |
2336 KB |
manual_j3.txt |
AC |
22 ms |
796 KB |
manual_j4.txt |
AC |
24 ms |
768 KB |
manual_j5.txt |
AC |
24 ms |
920 KB |
manual_j6.txt |
AC |
24 ms |
916 KB |
manual_j7.txt |
AC |
25 ms |
760 KB |
manual_j8.txt |
AC |
23 ms |
920 KB |
manual_j9.txt |
AC |
22 ms |
800 KB |
manual_k1.txt |
AC |
33 ms |
3104 KB |
manual_k2.txt |
AC |
29 ms |
3060 KB |
random_01.txt |
AC |
30 ms |
2720 KB |
random_02.txt |
AC |
32 ms |
2536 KB |
random_03.txt |
AC |
31 ms |
2336 KB |
random_04.txt |
AC |
34 ms |
2204 KB |
random_05.txt |
AC |
28 ms |
1828 KB |
random_06.txt |
AC |
28 ms |
1828 KB |
random_max_01.txt |
AC |
38 ms |
3444 KB |
random_max_02.txt |
AC |
36 ms |
3232 KB |
random_max_03.txt |
AC |
31 ms |
3100 KB |
random_max_04.txt |
AC |
36 ms |
2976 KB |
random_max_05.txt |
AC |
35 ms |
2848 KB |
random_max_06.txt |
AC |
37 ms |
2704 KB |
random_max_07.txt |
AC |
34 ms |
2600 KB |
random_max_08.txt |
AC |
32 ms |
2468 KB |
random_max_09.txt |
AC |
32 ms |
2468 KB |
random_max_10.txt |
AC |
29 ms |
2336 KB |
sample_01.txt |
AC |
21 ms |
924 KB |
sample_02.txt |
AC |
24 ms |
800 KB |
sample_03.txt |
AC |
23 ms |
808 KB |
sample_04.txt |
AC |
24 ms |
924 KB |
white_01.txt |
AC |
40 ms |
3364 KB |
white_02.txt |
AC |
35 ms |
3364 KB |
white_03.txt |
AC |
37 ms |
3488 KB |
white_04.txt |
AC |
37 ms |
3620 KB |