#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
using namespace std;
//1 : 동
//2 : 서
//3 : 남
//4 : 북
int mini,dap=2147483647,n,w,h,d[10][10][510][510],px,py,pk,check[510][510];
bool ch[5][510][510];
int xx[5]={0,0,0,1,-1};
int yy[5]={0,1,-1,0,0};
char b[510],a[510][510];
vector< pair<short,short> >arr[250010];
struct data
{
short x,y;
}go[5][510][510];
struct data2
{
int x,y,lev;
}q[250010];
struct data3
{
int x,y;
}pos[11];
void bfs2(int i,int j,int p)
{
int k,f=-1,r=-1,kx,ky,l;
while(1)
{
f=-1, r=-1;
for(k=0;k<arr[p].size();k++)
{
if(check[arr[p][k].first][arr[p][k].second]) continue;
r++; q[r].x=arr[p][k].first; q[r].y=arr[p][k].second; q[r].lev=p; check[q[r].x][q[r].y]=q[r].lev;
}
arr[p].clear();
while(f!=r)
{
f++;
p=q[f].lev+1;
for(k=0;k<arr[p].size();k++)
{
if(check[arr[p][k].first][arr[p][k].second]) continue;
r++; q[r].x=arr[p][k].first; q[r].y=arr[p][k].second; q[r].lev=p; check[q[r].x][q[r].y]=q[r].lev;
}
arr[p].clear();
for(k=1;k<=4;k++)
{
kx=go[k][q[f].x][q[f].y].x; ky=go[k][q[f].x][q[f].y].y;
if(check[kx][ky]) continue;
r++;
q[r].x=kx; q[r].y=ky; q[r].lev=p; check[q[r].x][q[r].y]=q[r].lev;
}
}
for(p=p;p<=w*h;p++) if(arr[p].size()) break;
if(p==w*h+1) break;
}
for(k=1;k<=h;k++)
for(l=1;l<=w;l++)
if(check[k][l]) d[i][j][k][l]=check[k][l];
}
void dp()
{
int i,j,k,l,r;
for(i=1;i<=n-1;i++){
for(j=1;j<=n-i;j++){
memset(check,0,sizeof check); mini=2147483647;
for(r=j;r<j+i;r++){
for(k=1;k<=h;k++){
for(l=1;l<=w;l++){
if(r==j) d[j][j+i][k][l]=2147483647;
if(d[j][r][k][l]==2147483647 || d[r+1][j+i][k][l]==2147483647) continue;
else d[j][j+i][k][l]=min(d[j][j+i][k][l],d[j][r][k][l]+d[r+1][j+i][k][l]);
}
}
}
for(k=1;k<=h;k++){
for(l=1;l<=w;l++){
if(d[j][j+i][k][l]!=2147483647) arr[d[j][j+i][k][l]].push_back(make_pair(k,l));
if(mini>d[j][j+i][k][l]) mini=d[j][j+i][k][l];
}
}
if(mini!=2147483647) bfs2(j,j+i,mini);
}
}
}
void dfs(short k,short x,short y)
{
int i,l;
if(ch[k][x][y]==1 || a[x][y]==0 || a[x][y]=='x'){px=x; py=y; pk=k; return;}
ch[k][x][y]=1;
if(a[x][y]=='.' || ('1'<=a[x][y] && a[x][y]<='9')) dfs(k,x+xx[k],y+yy[k]);
else if(a[x][y]=='C'){
if(k==1) l=3; if(k==3) l=2; if(k==2) l=4; if(k==4) l=1;
dfs(l,x+xx[l],y+yy[l]);
}
else if(a[x][y]=='A'){
if(k==1) l=4; if(k==4) l=2; if(k==2) l=3; if(k==3) l=1;
dfs(l,x+xx[l],y+yy[l]);
}
if(ch[pk][px][py]==1) go[k][x][y].x=go[pk][px][py].x, go[k][x][y].y=go[pk][px][py].y;
else go[k][x][y].x=x, go[k][x][y].y=y;
px=x; py=y; pk=k;
}
void bfs()
{
int i,j,f=-1,r=0,kx,ky,k;
for(i=1;i<=n;i++){
q[0].x=pos[i].x; q[0].y=pos[i].y; q[0].lev=0; f=-1; r=0; memset(check,0,sizeof check); check[pos[i].x][pos[i].y]=1;
while(f!=r){
f++;
for(j=1;j<=4;j++){
kx=go[j][q[f].x][q[f].y].x; ky=go[j][q[f].x][q[f].y].y;
if(check[kx][ky]==1) continue;
check[kx][ky]=1;
r++; q[r].x=kx; q[r].y=ky; q[r].lev=q[f].lev+1;
d[i][i][kx][ky]=q[r].lev;
}
}
for(j=1;j<=h;j++){
for(k=1;k<=w;k++){
if(d[i][i][j][k]==0 && (j!=pos[i].x || k!=pos[i].y)) d[i][i][j][k]=2147483647;
}
}
}
}
int main()
{
int i,j,k;
scanf("%d %d %d",&n,&w,&h);
for(i=1;i<=h;i++){
scanf("%s",b);
for(j=1;j<=w;j++){
a[i][j]=b[j-1];
if(1<=(a[i][j]-'0') && (a[i][j]-'0')<=9) pos[a[i][j]-'0'].x=i, pos[a[i][j]-'0'].y=j;
}
}
for(i=1;i<=h;i++)
for(j=1;j<=w;j++)
for(k=1;k<=4;k++)
dfs(k,i,j);
bfs();
dp();
for(i=1;i<=h;i++)
for(j=1;j<=w;j++)
if(dap>d[1][n][i][j]) dap=d[1][n][i][j];
if(dap==2147483647) printf("-1");
else printf("%d",dap);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
119220 KB |
Output is correct |
| 2 |
Correct |
4 ms |
119220 KB |
Output is correct |
| 3 |
Correct |
0 ms |
119220 KB |
Output is correct |
| 4 |
Correct |
4 ms |
119220 KB |
Output is correct |
| 5 |
Correct |
0 ms |
119220 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
119220 KB |
Output is correct |
| 2 |
Correct |
4 ms |
119220 KB |
Output is correct |
| 3 |
Correct |
0 ms |
119220 KB |
Output is correct |
| 4 |
Correct |
0 ms |
119220 KB |
Output is correct |
| 5 |
Correct |
0 ms |
119220 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
84 ms |
121624 KB |
Output is correct |
| 2 |
Correct |
12 ms |
119220 KB |
Output is correct |
| 3 |
Correct |
20 ms |
119220 KB |
Output is correct |
| 4 |
Correct |
132 ms |
122520 KB |
Output is correct |
| 5 |
Correct |
64 ms |
119916 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
124 ms |
119220 KB |
Output is correct |
| 2 |
Correct |
428 ms |
130176 KB |
Output is correct |
| 3 |
Correct |
112 ms |
121696 KB |
Output is correct |
| 4 |
Correct |
124 ms |
119220 KB |
Output is correct |
| 5 |
Correct |
288 ms |
127616 KB |
Output is correct |
