미로 속 로봇

아직 제출이 없습니다시간 제한1초메모리 제한128 MB

문제 설명

예제1

로봇이 미로에 갇혔다. 미로는 2차원 격자이고, 각 칸은 벽, 로봇이 지나갈 수 있는 빈 칸, 로봇의 출발 지점, 출구 중 하나다.

로봇은 한 번에 한 칸씩 위, 아래, 왼쪽, 오른쪽으로 움직인다. 대각선으로는 움직이지 못하고, 벽이 있는 칸에도 들어가지 못한다. 출구 칸 중 어느 곳에든 도착하면 미로를 빠져나간 것이 되고, 출발은 반드시 지정된 지점에서 한다.

로봇이 미로를 빠져나가는 데 필요한 최소 이동 횟수를 구하라.

첫 줄에 미로의 개수가 주어진다.

미로마다 먼저 두 정수 $R$ 과 $C$ 가 주어진다. $R$ 은 행의 개수, $C$ 는 열의 개수다. 이어지는 $R$ 개의 줄에는 각 행의 칸을 나타내는 문자열이 한 줄씩 주어진다.

한 미로에 출구가 두 개 이상 있을 수도 있다.

미로마다 한 줄씩, 입력에 주어진 순서대로 출력한다.

로봇이 미로를 빠져나갈 수 있으면 다음 형식으로 출력한다.

Shortest Path: t

여기서 $t$ 는 최단 경로의 길이, 즉 로봇이 움직이는 최소 횟수다.

빠져나갈 방법이 없으면 다음을 출력한다.

No Exit