미로 속 로봇
면접 대비시간 제한1초메모리 제한128 MB
각 격자 미로에서 S부터 G까지 상하좌우로 이동하는 가장 짧은 경로 길이를 구하고 출구가 없으면 없다고 보고합니다.
문제
로봇이 미로에 갇혔다. 미로는 2차원 격자이고, 각 칸은 벽, 로봇이 지나갈 수 있는 빈 칸, 로봇의 출발 지점, 출구 중 하나다.
로봇은 한 번에 한 칸씩 위, 아래, 왼쪽, 오른쪽으로 움직인다. 대각선으로는 움직이지 못하고, 벽이 있는 칸에도 들어가지 못한다. 출구 칸 중 어느 곳에든 도착하면 미로를 빠져나간 것이 되고, 출발은 반드시 지정된 지점에서 한다.
로봇이 미로를 빠져나가는 데 필요한 최소 이동 횟수를 구하라.
입력
첫 줄에 미로의 개수가 주어진다.
미로마다 먼저 두 정수 과 가 주어진다. 은 행의 개수, 는 열의 개수다. 이어지는 개의 줄에는 각 행의 칸을 나타내는 문자열이 한 줄씩 주어진다.
X는 로봇이 지나갈 수 없는 장애물O또는0은 로봇이 지나갈 수 있는 빈 칸S는 로봇의 출발 위치G는 출구
한 미로에 출구가 두 개 이상 있을 수도 있다.
출력
미로마다 한 줄씩, 입력에 주어진 순서대로 출력한다.
로봇이 미로를 빠져나갈 수 있으면 다음 형식으로 출력한다.
Shortest Path: t
여기서 는 최단 경로의 길이, 즉 로봇이 움직이는 최소 횟수다.
빠져나갈 방법이 없으면 다음을 출력한다.
No Exit