세영이가 미로 탈출 로봇 대회에 참가하였다.

미로는 NxN 크기의 격자로 된 판 위에 장애물이 있고 미로는 로봇이 밖으로 나가지 못하게 벽으로 둘러 쌓여있다.

이 대회는 좀 특이하게 미로를 빠져 나가는 것이 아니라 가장 먼 거리를 찾아 가는 로봇이 우승을 하게 된다.

대회의 규칙은 다음과 같다.

로봇은 상, 하, 좌, 우 아무방향이나 움직일 수 있으나. 한번 지나간 길을 다시 갈 수 없으며, 장애물이나 벽 앞에서만 방향을 바꿀 수 있다.

다음은 6x6 크기의 미로에 4개의 장애물이 있는 예이다.

위 예제의 각 거리는 그림 1은 20, 그림 2는 18, 그림 3은 22, 그림 4는 26으로 그림 4번이 가장 먼 거리가 된다.

우승을 하려면 세영이의 로봇이 얼마나 먼 거리를 가야 하는지 구하여 보자.

가장 먼 거리 찾기 timer 1s memory 128MB

가장 먼 거리 찾기 1s 128MB