지정된 좌표에서 시작해서 상하좌우 방향으로 진행할 때, 가장 많은 칸을 밟을 수 있는 것이 답이 된다.
이전 포스팅과 비슷한 문제이긴 하다.
방향이 좌표당 4개가 있기 때문에 해당 방향으로 또 방문한다면 이를 사이클로 보자.
사이클이 존재한다면 무한히 반복할 수 있기 때문에 Voyager를 출력해야 한다. 단, 그 무한히 반복할 수 있을 때의 처음 방향을 출력해야 한다. 가령 오른쪽으로 시작했을 때 반복이 된다면 아래처럼 출력한다.
#include <cstdio>
#include <cstring>
int main() {
char board[500][501], dirp[]="URDL";
int N, M, i, j, dy[] = { -1,0,1,0 }, dx[] = { 0,1,0,-1 }, ans = 0, dir = 0, vi[500][501][4],t,sy,sx,cy,cx,d,ty,tx,td;
bool cycle = 0;
scanf("%d%d", &N, &M);
for (i = 0; i < N; i++) scanf("%s", board[i]);
scanf("%d%d", &sy, &sx);
sy--, sx--;
for (i = 0; i < 4; i++) {
memset(vi, 0, sizeof vi);
cy = sy, cx = sx;
t = vi[cy][cx][i] = 1, td = d = i;
while (1) {
ty = cy + dy[d], tx = cx + dx[d];
if (!(0 <= ty && ty < N && 0 <= tx && tx < M && board[ty][tx] != 'C')) break;
if (board[ty][tx] != '.') {
if (board[ty][tx] == '/') td = (d + (d % 2 ? 3 : 1)) % 4;
else {
switch (d) {
case 0: td = 3; break;
case 1: td = 2; break;
case 2: td = 1; break;
case 3: td = 0; break;
}
}
}
if (vi[ty][tx][td]) {
cycle = 1;
dir = i;
break;
}
vi[ty][tx][td] = vi[cy][cx][d] + 1;
t++;
cy = ty, cx = tx, d = td;
}
if (ans < t) {
ans = t, dir = i;
if (cycle) break;
}
}
printf("%c\n", dirp[dir]);
if (cycle) puts("Voyager");
else printf("%d", ans);
return 0;
}