#include <stdio.h>
#include <vector>
#include <queue>
#define INF 0x7fffffff
using namespace std;
typedef pair <int,int> ppair;
typedef pair <int,ppair> pppair;
priority_queue <pppair,vector<pppair>,greater<pppair> > Q;
int N, W, H, Ynext[501][501][4], Xnext[501][501][4], Yloc[10], Xloc[10];
int Ydir[4]={0,1,0,-1}, Xdir[4]={1,0,-1,0}, D[10][10][501][501], Ans=INF;
char Room[501][502];
void renew(int p, int q) {
int i, j, cost, y, x;
for(i=1 ; i<=H ; i++)
for(j=1 ; j<=W ; j++)
if(D[p][q][i][j]!=INF)
Q.push(make_pair(D[p][q][i][j],make_pair(i,j)));
while(!Q.empty()) {
cost=Q.top().first;
y=Q.top().second.first;
x=Q.top().second.second;
Q.pop();
if(cost!=D[p][q][y][x])
continue;
for(i=0 ; i<=3 ; i++)
if(D[p][q][Ynext[y][x][i]][Xnext[y][x][i]]>D[p][q][y][x]+1) {
D[p][q][Ynext[y][x][i]][Xnext[y][x][i]]=D[p][q][y][x]+1;
Q.push(make_pair(D[p][q][Ynext[y][x][i]][Xnext[y][x][i]],make_pair(Ynext[y][x][i],Xnext[y][x][i])));
}
}
}
int main(void) {
int i, j, k, l, y, x, dir, py, px;
scanf("%d %d %d",&N,&W,&H);
for(i=1 ; i<=H ; i++) {
scanf("%s",&Room[i][1]);
for(j=1 ; j<=W ; j++)
if('1'<=Room[i][j] && Room[i][j]<='9') {
Yloc[Room[i][j]-'0']=i;
Xloc[Room[i][j]-'0']=j;
Room[i][j]='.';
}
}
for(i=1 ; i<=H ; i++)
for(j=1 ; j<=W ; j++)
if(Room[i][j]!='x')
for(k=0 ; k<=3 ; k++)
{
y=i;
x=j;
dir=k;
while(y>=1 && y<=H && x>=1 && x<=W && Room[y][x]!='x') {
if(Room[y][x]=='A') {
dir--;
if(dir<0)
dir=3;
}
else if(Room[y][x]=='C') {
dir++;
dir%=4;
}
py=y;
px=x;
y+=Ydir[dir];
x+=Xdir[dir];
}
Ynext[i][j][k]=py;
Xnext[i][j][k]=px;
}
for(k=1 ; k<=N ; k++) {
for(i=1 ; i<=H ; i++)
for(j=1 ; j<=W ; j++)
D[k][k][i][j]=INF;
D[k][k][Yloc[k]][Xloc[k]]=0;
renew(k,k);
}
for(i=1 ; i<=N-1 ; i++)
for(j=i+1 ; j<=N ; j++)
for(y=1 ; y<=H ; y++)
for(x=1 ; x<=W ; x++)
D[i][j][y][x]=INF;
for(l=1 ; l<=N-1 ; l++)
for(i=1 ; i<=N-l ; i++) {
j=i+l;
for(k=i ; k<=j-1 ; k++)
for(y=1 ; y<=H ; y++)
for(x=1 ; x<=W ; x++)
if(D[i][k][y][x]!=INF && D[k+1][j][y][x]!=INF && D[i][j][y][x]>D[i][k][y][x]+D[k+1][j][y][x])
D[i][j][y][x]=D[i][k][y][x]+D[k+1][j][y][x];
renew(i,j);
}
for(i=1 ; i<=H ; i++)
for(j=1 ; j<=W ; j++)
if(Ans>D[1][N][i][j])
Ans=D[1][N][i][j];
printf("%d",Ans);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
107348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
107348 KB |
Output isn't correct |
| 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 |
- |
