Submission #306389
Source Code Expand
#include<stdio.h>
#include<vector>
#include<string.h>
#include<queue>
#include<algorithm>
using namespace std;
namespace MCF {
// required <string.h> <vector> <queue> <algorithm>
#define MAXN 110000
#define MAXM 110000
#define wint int
#define cint int
const wint wEPS = 0;
const wint wINF = 1001001001;
const cint cEPS = 0;
const cint cINF = 1001001001;
int col[MAXM];
int n, m, ptr[MAXN], next[MAXM], zu[MAXM];
wint capa[MAXM], tof;
cint cost[MAXM], toc, d[MAXN], pot[MAXN];
int vis[MAXN], pree[MAXN];
void init(int _n) {
n = _n; m = 0; memset(ptr, ~0, n * 4);
}
void ae(int u, int v, wint w, cint c) {
next[m] = ptr[u]; ptr[u] = m; zu[m] = v; capa[m] = w; cost[m] = +c;col[m]=0; ++m;
next[m] = ptr[v]; ptr[v] = m; zu[m] = u; capa[m] = 0; cost[m] = -c;col[m]=1; ++m;
}
bool solve(int src, int ink, wint flo = wINF) {
int i, u, v;
wint f;
cint c, cc;
memset(pot, 0, n * sizeof(cint));
//*
for (bool cont = 1; cont; ) {
cont = 0;
for (u = 0; u < n; ++u) for (i = ptr[u]; ~i; i = next[i]) if (capa[i] > wEPS) {
if (pot[zu[i]] > pot[u] + cost[i] + cEPS) {
pot[zu[i]] = pot[u] + cost[i]; cont = 1;
}
}
}
//*/
for (toc = 0, tof = 0; tof + wEPS < flo; ) {
typedef pair<cint,int> node;
priority_queue< node,vector<node>,greater<node> > q;
for (u = 0; u < n; ++u) { d[u] = cINF; vis[u] = 0; }
for (q.push(make_pair(d[src] = 0, src)); !q.empty(); ) {
c = q.top().first; u = q.top().second; q.pop();
if (vis[u]++) continue;
for (i = ptr[u]; ~i; i = next[i]) if (capa[i] > wEPS) {
cc = c + cost[i] + pot[u] - pot[v = zu[i]];
if (d[v] > cc + cEPS) { q.push(make_pair(d[v] = cc, v)); pree[v] = i; }
}
}
if (!vis[ink]) return 0;
f = flo - tof;
for (v = ink; v != src; v = zu[i ^ 1]) { i = pree[v]; f=min(f,capa[i]); }
for (v = ink; v != src; v = zu[i ^ 1]) { i = pree[v]; capa[i] -= f; capa[i ^ 1] += f; }
tof += f;
toc += f * (d[ink] - pot[src] + pot[ink]);
for (u = 0; u < n; ++u) pot[u] += d[u];
}
return 1;
}
}
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
char str[100][100];
int bfs[100][100];
int main(){
int a,b;
scanf("%d%d",&a,&b);
for(int i=0;i<a;i++)scanf("%s",str[i]);
for(int i=0;i<100;i++)for(int j=0;j<100;j++)bfs[i][j]=-1;
queue<pair<int,int> > Q;
int sr,sc;
int ar,ac;
int br,bc;
for(int i=0;i<a;i++)for(int j=0;j<b;j++){
if(str[i][j]=='S'){sr=i;sc=j;}
if(str[i][j]=='A'){ar=i;ac=j;}
if(str[i][j]=='B'){br=i;bc=j;}
}
Q.push(make_pair(sr,sc));
bfs[sr][sc]=0;
while(Q.size()){
int row=Q.front().first;
int col=Q.front().second;
Q.pop();
for(int i=0;i<4;i++){
if(0<=row+dx[i]&&row+dx[i]<a&&0<=col+dy[i]&&col+dy[i]<b&&!~bfs[row+dx[i]][col+dy[i]]&&str[row+dx[i]][col+dy[i]]!='#'){
bfs[row+dx[i]][col+dy[i]]=bfs[row][col]+1;
Q.push(make_pair(row+dx[i],col+dy[i]));
}
}
}
int ad=bfs[ar][ac];
int bd=bfs[br][bc];
MCF::init(a*b*2+1);
for(int i=0;i<a;i++)for(int j=0;j<b;j++){
MCF::ae(2*(i*b+j),2*(i*b+j)+1,1,0);
for(int k=0;k<4;k++){
if(0<=i+dx[k]&&i+dx[k]<a&&0<=j+dy[k]&&j+dy[k]<b&&str[i+dx[k]][j+dy[k]]!='#'){
MCF::ae(2*(i*b+j)+1,2*((i+dx[k])*b+j+dy[k]),1,1);
}
}
}
MCF::ae(2*(ar*b+ac)+1,a*b*2,1,0);
MCF::ae(2*(br*b+bc)+1,a*b*2,1,0);
int res=MCF::solve(2*(sr*b+sc)+1,a*b*2,2);
if(!res||MCF::toc>ad+bd){
printf("NA\n");return 0;
}
int nr=ar;
int nc=ac;
while(1){
int t=2*(nr*b+nc);
int to;
for(int i=MCF::ptr[t];~i;i=MCF::next[i]){
if(MCF::col[i]&&MCF::capa[i]){
to=MCF::zu[i]/2;
break;
}
}
int tr=to/b;
int tc=to%b;
if(sr==tr&&sc==tc)break;
str[tr][tc]='a';
nr=tr;nc=tc;
}
nr=br;
nc=bc;
while(1){
int t=2*(nr*b+nc);
int to;
for(int i=MCF::ptr[t];~i;i=MCF::next[i]){
if(MCF::col[i]&&MCF::capa[i]){
to=MCF::zu[i]/2;
break;
}
}
int tr=to/b;
int tc=to%b;
if(sr==tr&&sc==tc)break;
str[tr][tc]='b';
nr=tr;nc=tc;
}
for(int i=0;i<a;i++)printf("%s\n",str[i]);
}
Submission Info
Submission Time
2014-12-21 17:11:08+0900
Task
D - Maze
User
tozangezan
Language
C++ (G++ 4.6.4)
Score
100
Code Size
4074 Byte
Status
AC
Exec Time
29 ms
Memory
1568 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:73:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:74:40: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
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
920 KB
manual_j10.txt
AC
24 ms
804 KB
manual_j11.txt
AC
24 ms
1452 KB
manual_j12.txt
AC
24 ms
800 KB
manual_j13.txt
AC
24 ms
804 KB
manual_j14.txt
AC
23 ms
924 KB
manual_j15.txt
AC
24 ms
796 KB
manual_j2.txt
AC
28 ms
1184 KB
manual_j3.txt
AC
23 ms
924 KB
manual_j4.txt
AC
23 ms
800 KB
manual_j5.txt
AC
24 ms
876 KB
manual_j6.txt
AC
22 ms
800 KB
manual_j7.txt
AC
23 ms
924 KB
manual_j8.txt
AC
26 ms
924 KB
manual_j9.txt
AC
24 ms
800 KB
manual_k1.txt
AC
27 ms
1448 KB
manual_k2.txt
AC
25 ms
1564 KB
random_01.txt
AC
24 ms
1440 KB
random_02.txt
AC
26 ms
1308 KB
random_03.txt
AC
24 ms
1308 KB
random_04.txt
AC
25 ms
1192 KB
random_05.txt
AC
29 ms
1120 KB
random_06.txt
AC
24 ms
1176 KB
random_max_01.txt
AC
24 ms
1560 KB
random_max_02.txt
AC
25 ms
1440 KB
random_max_03.txt
AC
25 ms
1436 KB
random_max_04.txt
AC
27 ms
1440 KB
random_max_05.txt
AC
26 ms
1312 KB
random_max_06.txt
AC
26 ms
1440 KB
random_max_07.txt
AC
24 ms
1308 KB
random_max_08.txt
AC
26 ms
1436 KB
random_max_09.txt
AC
26 ms
1440 KB
random_max_10.txt
AC
26 ms
1440 KB
sample_01.txt
AC
22 ms
932 KB
sample_02.txt
AC
22 ms
796 KB
sample_03.txt
AC
24 ms
804 KB
sample_04.txt
AC
23 ms
796 KB
white_01.txt
AC
25 ms
1440 KB
white_02.txt
AC
26 ms
1568 KB
white_03.txt
AC
27 ms
1440 KB
white_04.txt
AC
26 ms
1568 KB