#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[11][11][510][510],ch[5][510][510],px,py,pk,check[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<int,int> >arr[250010];
struct data
{
int 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;
for(k=0;k<arr[p].size();k++)
{
r++; q[r].x=arr[p][k].first; q[r].y=arr[p][k].second; q[r].lev=d[i][j][q[r].x][q[r].y]; 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=q[f].lev+1; 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=q[f].lev+1; check[q[r].x][q[r].y]=q[r].lev;
}
}
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) d[j][j+i][k][l]=2147483647;
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];
}
}
bfs2(j,j+i,mini);
}
}
}
void dfs(int k,int x,int 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];
}
}
printf("%d",dap);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
149448 KB |
Output is correct |
| 2 |
Runtime error |
0 ms |
149444 KB |
SIGSEGV Segmentation fault |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
