Submission #306875
Source Code Expand
#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <cstring>
#include <functional>
#include <cmath>
#include <utility>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define rep1(i,n) for(int i=1;i<=(n);++i)
#define all(c) (c).begin(),(c).end()
#define fs first
#define sc second
#define pb push_back
#define show(x) cout << #x << " " << x << endl
typedef pair<int,int> P;
struct edge {int to,cap,cost,rev;};
const int MAX_V=10000,INF=1e8;
int V;
vector<edge> G[MAX_V];
int h[MAX_V];
int dist[MAX_V];
int prevv[MAX_V],preve[MAX_V];
void add_edge(int from, int to, int cap, int cost){
edge e1={to,cap,cost,G[to].size()},e2={from,0,-cost,G[from].size()};
G[from].push_back(e1);
G[to].push_back(e2);
}
int min_cost_flow(int s, int t, int f){
int res=0;
fill(h,h+V,0);
while(f>0){
priority_queue< P,vector<P>,greater<P> > que;
fill(dist,dist+V,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<G[v].size();i++){
edge &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<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;
}
string s[50];
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int H,W;
bool is(int x,int y){
return 0<=x&&x<H&&0<=y&&y<W&&s[x][y]!='#';
}
int d[50][50];
void bfs(int sx,int sy){
queue<P> que;
que.push(P(sx,sy));
rep(i,H) rep(j,W) d[i][j]=INF;
d[sx][sy]=0;
while(!que.empty()){
P p=que.front();
que.pop();
int x=p.fs,y=p.sc;
rep(di,4){
int nx=x+dx[di],ny=y+dy[di];
if(!is(nx,ny)) continue;
if(d[nx][ny]!=INF) continue;
d[nx][ny]=d[x][y]+1;
que.push(P(nx,ny));
}
}
}
int in(int x,int y){
return (x*W+y)*2;
}
int out(int x,int y){
return (x*W+y)*2+1;
}
int main(){
cin>>H>>W;
rep(i,H) cin>>s[i];
int sx,sy;
rep(i,H) rep(j,W) if(s[i][j]=='S') sx=i,sy=j;
bfs(sx,sy);
rep(i,H) rep(j,W) rep(di,4){
if(s[i][j]=='#') continue;
int nx=i+dx[di],ny=j+dy[di];
if(!is(nx,ny)) continue;
add_edge(out(nx,ny),in(i,j),1,1);
}
rep(i,H) rep(j,W){
int tt=1;
if(s[i][j]=='S') tt=2;
add_edge(in(i,j),out(i,j),tt,0);
}
int S=H*W*2,T=S+1;
V=T+1;
int ax,ay,bx,by;
int da,db;
rep(i,H) rep(j,W){
if(s[i][j]=='S'){
add_edge(S,in(i,j),2,0);
}
if(s[i][j]=='A'){
add_edge(out(i,j),T,1,0);
da=d[i][j];
ax=i,ay=j;
}
if(s[i][j]=='B'){
add_edge(out(i,j),T,1,0);
db=d[i][j];
bx=i,by=j;
}
}
// show(da);
// show(db);
int f=da+db;
if(f>=INF){
puts("NA");
return 0;
}
int t=min_cost_flow(S,T,2);
if(t!=f){
puts("NA");
return 0;
}
int x=ax,y=ay;
while(s[x][y]!='S'){
for(auto e:G[in(x,y)]){
if(e.to>=S) continue;
if(e.cap==1){
x=(e.to)/2/W,y=(e.to)/2%W;
if(s[x][y]!='S') s[x][y]='a';
break;
}
}
}
x=bx,y=by;
while(s[x][y]!='S'){
for(auto e:G[in(x,y)]){
if(e.to>=S) continue;
if(e.cap==1){
x=(e.to)/2/W,y=(e.to)/2%W;
if(s[x][y]!='S') s[x][y]='b';
break;
}
}
}
rep(i,H) cout<<s[i]<<endl;
}
Submission Info
Submission Time |
|
Task |
D - Maze |
User |
sigma425 |
Language |
C++11 (GCC 4.8.1) |
Score |
100 |
Code Size |
3656 Byte |
Status |
AC |
Exec Time |
32 ms |
Memory |
1976 KB |
Compile Error
./Main.cpp: In function ‘void add_edge(int, int, int, int)’:
./Main.cpp:31:34: warning: narrowing conversion of ‘G[to].std::vector<_Tp, _Alloc>::size<edge, std::allocator<edge> >()’ from ‘std::vector<edge>::size_type {aka long unsigned int}’ to ‘int’ inside { } [-Wnarrowing]
edge e1={to,cap,cost,G[to].size()},e2={from,0,-cost,G[from].size()};
^
./Main.cpp:31:67: warning: narrowing conversion of ‘G[from].std::vector<_Tp, _Alloc>::size<edge, std::allocator<edge> >()’ from ‘std::vector<edge>::size_type {aka long unsigned int}’ to ‘int’ inside { } [-Wnarrowing]
edge e1={to,cap,cost,G[to].size()},e2={from,0,-cost,G[from].size()};
^
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 |
1080 KB |
manual_j10.txt |
AC |
25 ms |
1128 KB |
manual_j11.txt |
AC |
31 ms |
1852 KB |
manual_j12.txt |
AC |
25 ms |
1080 KB |
manual_j13.txt |
AC |
25 ms |
1172 KB |
manual_j14.txt |
AC |
25 ms |
1184 KB |
manual_j15.txt |
AC |
26 ms |
1308 KB |
manual_j2.txt |
AC |
27 ms |
1568 KB |
manual_j3.txt |
AC |
25 ms |
1180 KB |
manual_j4.txt |
AC |
26 ms |
1176 KB |
manual_j5.txt |
AC |
25 ms |
1180 KB |
manual_j6.txt |
AC |
28 ms |
1180 KB |
manual_j7.txt |
AC |
24 ms |
1072 KB |
manual_j8.txt |
AC |
24 ms |
1084 KB |
manual_j9.txt |
AC |
27 ms |
1180 KB |
manual_k1.txt |
AC |
32 ms |
1848 KB |
manual_k2.txt |
AC |
32 ms |
1848 KB |
random_01.txt |
AC |
30 ms |
1720 KB |
random_02.txt |
AC |
29 ms |
1512 KB |
random_03.txt |
AC |
29 ms |
1444 KB |
random_04.txt |
AC |
32 ms |
1564 KB |
random_05.txt |
AC |
31 ms |
1560 KB |
random_06.txt |
AC |
30 ms |
1560 KB |
random_max_01.txt |
AC |
30 ms |
1844 KB |
random_max_02.txt |
AC |
30 ms |
1848 KB |
random_max_03.txt |
AC |
31 ms |
1884 KB |
random_max_04.txt |
AC |
32 ms |
1816 KB |
random_max_05.txt |
AC |
28 ms |
1724 KB |
random_max_06.txt |
AC |
31 ms |
1820 KB |
random_max_07.txt |
AC |
29 ms |
1696 KB |
random_max_08.txt |
AC |
29 ms |
1592 KB |
random_max_09.txt |
AC |
28 ms |
1596 KB |
random_max_10.txt |
AC |
28 ms |
1468 KB |
sample_01.txt |
AC |
25 ms |
1184 KB |
sample_02.txt |
AC |
25 ms |
1172 KB |
sample_03.txt |
AC |
26 ms |
1216 KB |
sample_04.txt |
AC |
27 ms |
1176 KB |
white_01.txt |
AC |
30 ms |
1848 KB |
white_02.txt |
AC |
30 ms |
1976 KB |
white_03.txt |
AC |
29 ms |
1972 KB |
white_04.txt |
AC |
29 ms |
1852 KB |