Submission #15994

#TimeUsernameProblemLanguageResultExecution timeMemory
15994myungwooPortals (BOI14_portals)C++14
0 / 100
0 ms26220 KiB
#include <bits/stdc++.h> using namespace std; int yy[]={-1, 0, 1, 0}, xx[]={0, 1, 0, -1}; int N, M; int sy, sx, ey, ex; int D[1001][1001], E[1001][1001], F[1002][1002][4]; char A[1001][1002]; struct Z{ int d, y, x; bool operator < (const Z &ot)const{ return d > ot.d; } }; inline bool can_move(int y, int x){ return !(y < 1 || y > N || x < 1 || x > M || A[y][x] == '#'); } void portal_bfs() { queue <int> que; for (int i=1;i<=N;i++) for (int j=1;j<=M;j++) if (can_move(i, j)){ bool sw = 0; for (int d=0;d<4;d++){ int ny = i+yy[d], nx = j+xx[d]; if (!can_move(ny, nx)){ sw = 1; break; } } if (!sw) continue; E[i][j] = 0; que.push(i), que.push(j); } while (!que.empty()){ int y = que.front(); que.pop(); int x = que.front(); que.pop(); for (int d=0;d<4;d++){ int ny = y+yy[d], nx = x+xx[d]; if (!can_move(ny, nx)) continue; if (E[ny][nx] == 2e9) E[ny][nx] = E[y][x]+1, que.push(ny), que.push(nx); } } } int main() { scanf("%d%d", &N, &M); for (int i=1;i<=N;i++) scanf("%s", A[i]+1); for (int i=1;i<=N;i++) for (int j=1;j<=M;j++){ D[i][j] = E[i][j] = 2e9; if (A[i][j] == 'S') sy = i, sx = j; if (A[i][j] == 'C') ey = i, ex = j; } for (int i=1;i<=N;i++) for (int j=1;j<=N;j++){ F[i][j][0] = A[i][j] == '#' ? 0 : F[i-1][j][0]+1; F[i][j][3] = A[i][j] == '#' ? 1 : F[i][j-1][3]+1; } for (int i=N;i;i--) for (int j=M;j;j--){ F[i][j][1] = A[i][j] == '#' ? 0 : F[i][j+1][1]+1; F[i][j][2] = A[i][j] == '#' ? 0 : F[i+1][j][1]+1; } portal_bfs(); priority_queue <Z> que; D[sy][sx] = 0; que.push({0, sy, sx}); while (!que.empty()){ Z q = que.top(); que.pop(); if (q.d != D[q.y][q.x]) continue; for (int d=0;d<4;d++){ int y = q.y+yy[d], x = q.x+xx[d]; if (!can_move(y, x)) continue; if (D[y][x] > q.d+1) D[y][x] = q.d+1, que.push({D[y][x], y, x}); y = q.y + yy[d] * (F[q.y][q.x][d]-1); x = q.x + xx[d] * (F[q.y][q.x][d]-1); if (D[y][x] > q.d+E[q.y][q.x]+1) D[y][x] = q.d+E[q.y][q.x]+1, que.push({D[y][x], y, x}); } } printf("%d\n", D[ey][ex]); }
#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...