이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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];
char A[1001][1002];
inline bool can_move(int y, int x){ return !(y < 1 || y > N || x < 1 || x > M || A[y][x] == '#'); }
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] = 2e9;
if (A[i][j] == 'S') sy = i, sx = j;
if (A[i][j] == 'C') ey = i, ex = j;
}
queue <int> que;
que.push(sy); que.push(sx); D[sy][sx] = 0;
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) && D[ny][nx] == 2e9)
D[ny][nx] = D[y][x]+1, que.push(ny), que.push(nx);
if (!can_move(ny, nx)){
int ty = y, tx = x;
for (;;){
ny = ty+yy[(d+2)%4], nx = tx+xx[(d+2)%4];
if (!can_move(ny, nx)) break;
ty = ny, tx = nx;
}
if (D[ty][tx] == 2e9)
D[ty][tx] = D[y][x]+1, que.push(ty), que.push(tx);
}
}
}
printf("%d\n", D[ey][ex]);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |