Submission #15993

#TimeUsernameProblemLanguageResultExecution timeMemory
15993myungwooPortals (BOI14_portals)C++14
70 / 100
1000 ms14556 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]; 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; } 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}); for (;;){ int ny = y+yy[d], nx = x+xx[d]; if (!can_move(ny, nx)) break; y = ny, x = nx; } 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...