제출 #12714

#제출 시각아이디문제언어결과실행 시간메모리
12714baneling100로봇 (APIO13_robots)C++98
0 / 100
0 ms107348 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...