Submission #306033
Source Code Expand
/*
Author : ChnLich
*/
#include<cstdio>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<iostream>
#include<sstream>
#include<fstream>
#include<algorithm>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<deque>
#include<set>
#include<map>
#include<string>
#include<bitset>
#include<functional>
#include<utility>
using namespace std;
typedef long long llint;
typedef pair<int,int> ipair;
typedef unsigned int uint;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
const int MOD=1000000007,dx[]={0,1,0,-1},dy[]={1,0,-1,0};
const double eps=1e-8;
void read(int &k)
{
k=0; char x=getchar();
while(x<'0'||x>'9') x=getchar();
while(x>='0'&&x<='9') { k=k*10-48+x; x=getchar(); }
}
#define MAXN 5010
#define MAXM 500000
char s[55][55];
int n,m,S,p,q;
int vis[5010],dist[5010],last[5010];
int dd[2500*2500+10],ll,rr;
struct graph
{
int a[MAXN],b[MAXM],c[MAXM],d[MAXM],e[MAXM],l[MAXM],p;
int fare;
void clear()
{
memset(a,0,sizeof a);
p=1;
}
void addedge(int x,int y,int z=0,int w=0)
{
//if(z)printf("%d %d %d %d\n",x,y,z,w);
c[++p]=a[x]; a[x]=p; b[p]=y; d[p]=z; e[p]=w; l[p]=d[p];
c[++p]=a[y]; a[y]=p; b[p]=x; d[p]=0; e[p]=-w; l[p]=d[p];
}
void bfs(int S)
{
for(vis[dd[ll=rr=0]=S]=1;ll<=rr;ll++)
for(int i=a[dd[ll]];i;i=c[i]) if (!vis[b[i]])
vis[dd[++rr]=b[i]]=vis[dd[ll]]+1;
}
int spfa()
{
memset(dist,63,sizeof dist);
memset(vis,0,sizeof vis);
dist[0]=0;
for(vis[dd[ll=rr=0]=0]=1;ll<=rr;ll++)
{
vis[dd[ll]]=0;
for(int i=a[dd[ll]];i;i=c[i]) if (d[i]&&dist[b[i]]>dist[dd[ll]]+e[i])
{
dist[b[i]]=dist[dd[ll]]+e[i];
last[b[i]]=i;
if (!vis[b[i]])
{
vis[b[i]]=1;
dd[++rr]=b[i];
}
}
}
int now=n*m*2+1;
if (dist[now]>=1000000000) return 0;
fare=0;
while(now)
{
fare+=e[last[now]];
d[last[now]]-=1;
d[last[now]^1]+=1;
now=b[last[now]^1];
}
return 1;
}
int minfare()
{
int ret=0;
fare=0;
while(spfa())
ret+=fare;
return ret;
}
int dfs(int S)
{
int col;
int tx=(S-1)/m+1;
int ty=(S-1)%m+1;
for(int i=a[S];i;i=c[i]) if (d[i]<l[i])
{
col=dfs(b[i]);
if (b[i]==S+n*m)
if (s[tx][ty]=='.') s[tx][ty]=col;
}
if (S==::p) col='a';
if (S==q) col='b';
return col;
}
} A,B;
int getpos(int x,int y)
{
return (x-1)*m+y;
}
int main()
{
//freopen("D.in","r",stdin);
A.clear();
B.clear();
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) if (s[i][j]!='#')
{
if (s[i][j]=='S')
S=getpos(i,j);
else if (s[i][j]=='A')
p=getpos(i,j);
else if (s[i][j]=='B')
q=getpos(i,j);
for(int dir=0;dir<4;dir++)
{
int tx,ty;
tx=i+dx[dir];
ty=j+dy[dir];
if (tx>0&&tx<=n&&ty>0&&ty<=m&&s[tx][ty]!='#')
{
A.addedge(getpos(i,j),getpos(tx,ty));
B.addedge(n*m+getpos(i,j),getpos(tx,ty),1,0);
}
}
B.addedge(getpos(i,j),n*m+getpos(i,j),1,1);
}
A.bfs(S);
if (vis[p]>=1000000000||vis[q]>=1000000000)
{
puts("NA");
return 0;
}
int tot=vis[p]+vis[q]-2;
B.addedge(0,S+n*m,2,0);
B.addedge(p+n*m,n*m*2+1,1,0);
B.addedge(q+n*m,n*m*2+1,1,0);
int ret=B.minfare();
if (tot!=ret)
{
puts("NA");
return 0;
}
B.dfs(0);
for(int i=1;i<=n;i++,puts(""))
for(int j=1;j<=m;j++) printf("%c",s[i][j]);
return 0;
}
Submission Info
Submission Time
2014-12-21 16:07:42+0900
Task
D - Maze
User
asian-2014-2027
Language
C++ (G++ 4.6.4)
Score
100
Code Size
3558 Byte
Status
AC
Exec Time
28 ms
Memory
1824 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:143:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:144:42: 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
25 ms
924 KB
manual_j10.txt
AC
23 ms
1052 KB
manual_j11.txt
AC
27 ms
1824 KB
manual_j12.txt
AC
24 ms
928 KB
manual_j13.txt
AC
25 ms
1052 KB
manual_j14.txt
AC
25 ms
928 KB
manual_j15.txt
AC
25 ms
944 KB
manual_j2.txt
AC
25 ms
1440 KB
manual_j3.txt
AC
24 ms
924 KB
manual_j4.txt
AC
24 ms
924 KB
manual_j5.txt
AC
24 ms
1056 KB
manual_j6.txt
AC
25 ms
928 KB
manual_j7.txt
AC
23 ms
924 KB
manual_j8.txt
AC
23 ms
792 KB
manual_j9.txt
AC
23 ms
920 KB
manual_k1.txt
AC
27 ms
1652 KB
manual_k2.txt
AC
26 ms
1688 KB
random_01.txt
AC
26 ms
1432 KB
random_02.txt
AC
26 ms
1304 KB
random_03.txt
AC
25 ms
1436 KB
random_04.txt
AC
27 ms
1436 KB
random_05.txt
AC
25 ms
1188 KB
random_06.txt
AC
25 ms
1304 KB
random_max_01.txt
AC
27 ms
1700 KB
random_max_02.txt
AC
28 ms
1700 KB
random_max_03.txt
AC
28 ms
1568 KB
random_max_04.txt
AC
26 ms
1564 KB
random_max_05.txt
AC
27 ms
1692 KB
random_max_06.txt
AC
27 ms
1436 KB
random_max_07.txt
AC
28 ms
1440 KB
random_max_08.txt
AC
26 ms
1444 KB
random_max_09.txt
AC
27 ms
1432 KB
random_max_10.txt
AC
27 ms
1320 KB
sample_01.txt
AC
26 ms
928 KB
sample_02.txt
AC
26 ms
920 KB
sample_03.txt
AC
25 ms
804 KB
sample_04.txt
AC
24 ms
924 KB
white_01.txt
AC
28 ms
1696 KB
white_02.txt
AC
28 ms
1704 KB
white_03.txt
AC
27 ms
1696 KB
white_04.txt
AC
26 ms
1820 KB