제출 #7193

#제출 시각아이디문제언어결과실행 시간메모리
7193baneling100포탈들 (BOI14_portals)C++98
0 / 100
0 ms28640 KiB
#include <stdio.h> #include <queue> #define INF 0x7fffffff using namespace std; queue <int> Q; int R, C, Sy, Sx, Cy, Cx, A[1001][1001], B[1001][1001], D[1001][1001]; int Dy[4]={0,1,0,-1}, Dx[4]={1,0,-1,0}; int Left[1001][1001], Right[1001][1001], Up[1001][1001], Down[1001][1001]; void input(void) { int i, j, x; char temp[1002]; scanf("%d %d",&R,&C); for(i=1 ; i<=R ; i++) { scanf("%s",&temp[1]); for(j=1 ; j<=C ; j++) { if(temp[j]=='#') A[i][j]=1; else if(temp[j]=='S') { Sy=i; Sx=j; } else if(temp[j]=='C') { Cy=i; Cx=j; } B[i][j]=D[i][j]=INF; } } for(i=1 ; i<=R ; i++) { x=0; for(j=1 ; j<=C ; j++) { if(A[i][j]) x=0; else { if(!x) x=j; Left[i][j]=x; } } x=0; for(j=C ; j>=1 ; j--) { if(A[i][j]) x=0; else { if(!x) x=j; Right[i][j]=x; } } } for(i=1 ; i<=C ; i++) { x=0; for(j=1 ; j<=R ; j++) { if(A[j][i]) x=0; else { if(!x) x=j; Up[i][j]=x; } } x=0; for(j=R ; j>=1 ; j--) { if(A[i][j]) x=0; else { if(!x) x=j; Down[i][j]=x; } } } } void process(void) { int i, j, y, x, ty, tx; for(i=1 ; i<=R ; i++) for(j=1 ; j<=C ; j++) if(A[i][j]) { B[i][j]=0; Q.push(i); Q.push(j); } while(!Q.empty()) { y=Q.front(); Q.pop(); x=Q.front(); Q.pop(); for(i=0 ; i<=3 ; i++) { ty=y+Dy[i]; tx=x+Dx[i]; if(ty>=1 && ty<=R && tx>=1 && tx<=C) if(B[ty][tx]>B[y][x]+1) { B[ty][tx]=B[y][x]+1; Q.push(ty); Q.push(tx); } } } D[Sy][Sx]=0; Q.push(Sy); Q.push(Sx); while(!Q.empty()) { y=Q.front(); Q.pop(); x=Q.front(); Q.pop(); for(i=0 ; i<=3 ; i++) { ty=y+Dy[i]; tx=x+Dx[i]; if(ty>=1 && ty<=R && tx>=1 && tx<=C && !A[ty][tx]) if(D[ty][tx]>D[y][x]+1) { D[ty][tx]=D[y][x]+1; Q.push(ty); Q.push(tx); } } ty=y; tx=Left[y][x]; if(D[ty][tx]>D[y][x]+B[y][x]) { D[ty][tx]=D[y][x]+B[y][x]; Q.push(ty); Q.push(tx); } ty=y; tx=Right[y][x]; if(D[ty][tx]>D[y][x]+B[y][x]) { D[ty][tx]=D[y][x]+B[y][x]; Q.push(ty); Q.push(tx); } ty=Up[y][x]; tx=x; if(D[ty][tx]>D[y][x]+B[y][x]) { D[ty][tx]=D[y][x]+B[y][x]; Q.push(ty); Q.push(tx); } ty=Down[y][x]; tx=x; if(D[ty][tx]>D[y][x]+B[y][x]) { D[ty][tx]=D[y][x]+B[y][x]; Q.push(ty); Q.push(tx); } } } void output(void) { printf("%d",D[Cy][Cx]); } int main(void) { input(); process(); output(); 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...
#Verdict Execution timeMemoryGrader output
Fetching results...