About Monocycle ¶
외발자전거는 한 바퀴로 가는 자전거를 말한다. 다음 그림에 나와있는 것처럼 다섯 개의 서로 다른 색이 칠해져 있는 특별한 바퀴가 달려있는 외발자전거를 생각해보자.
http://online-judge.uva.es/p/v100/p10047a.gif
색이 칠해진 부분은 전부 똑같은 각도(72')만큼 벌어져 있다. 어떤 사람이 정사각형 타일로 만들어진 M × N 격자 위에서 이 외발자전거를 탄다. 한 타일의 중심에서 바로 옆 타일의 중심으로 외발자전거를 타고 이동하면 바퀴가 정확하게 72' 회전하게 되어있다. 위 그림을 보면 어떤 식인지 알 수 있을 것이다. 바퀴가 1번 타일의 중심에 있을 때, 파란색이 칠해진 부분의 중점이 바닥에 닿아있다. 바퀴가 다음 타일(2번 타일)중심으로 이동하면 흰색으로 칠해진 부분의 중점이 바닥에 닿게 된다.
http://online-judge.uva.es/p/v100/p10047b.gif
격자에 있는 정사각형 중 몇 개는 자전거가 갈 수 없게 막혀있다. 그 자전거를 탄 사람은 한 위치에서 시작해서 어떤 다른 위치로 최단 시간 안에 도착하려고 한다. 한 정사각형 위에서 그 자전거는 다음 정사각형으로 이동하거나, 같은 정사각형 내에서 왼쪽이나 오른쪽으로 90' 회전할 수 있다. 이런 동작을 하는 데 각각 1초가 걸린다. 자전거는 반드시 북쪽을 향하고, 바퀴에서 녹색 부분의 중점이 지면과 접하고 있는 상태에서 출발한다. 도착 지점에서는 자전거의 방향은 상관없지만 지면과 접하고 있는 부분은 녹색이어야 한다.
이 자전거를 타는 사람이 목적지에 도착할 수 있는지를 알아내고, 도착할 수 있다면 시간이 얼마나 걸리는지 계산해보자.
http://online-judge.uva.es/p/v100/p10047a.gif
색이 칠해진 부분은 전부 똑같은 각도(72')만큼 벌어져 있다. 어떤 사람이 정사각형 타일로 만들어진 M × N 격자 위에서 이 외발자전거를 탄다. 한 타일의 중심에서 바로 옆 타일의 중심으로 외발자전거를 타고 이동하면 바퀴가 정확하게 72' 회전하게 되어있다. 위 그림을 보면 어떤 식인지 알 수 있을 것이다. 바퀴가 1번 타일의 중심에 있을 때, 파란색이 칠해진 부분의 중점이 바닥에 닿아있다. 바퀴가 다음 타일(2번 타일)중심으로 이동하면 흰색으로 칠해진 부분의 중점이 바닥에 닿게 된다.
http://online-judge.uva.es/p/v100/p10047b.gif
격자에 있는 정사각형 중 몇 개는 자전거가 갈 수 없게 막혀있다. 그 자전거를 탄 사람은 한 위치에서 시작해서 어떤 다른 위치로 최단 시간 안에 도착하려고 한다. 한 정사각형 위에서 그 자전거는 다음 정사각형으로 이동하거나, 같은 정사각형 내에서 왼쪽이나 오른쪽으로 90' 회전할 수 있다. 이런 동작을 하는 데 각각 1초가 걸린다. 자전거는 반드시 북쪽을 향하고, 바퀴에서 녹색 부분의 중점이 지면과 접하고 있는 상태에서 출발한다. 도착 지점에서는 자전거의 방향은 상관없지만 지면과 접하고 있는 부분은 녹색이어야 한다.
이 자전거를 타는 사람이 목적지에 도착할 수 있는지를 알아내고, 도착할 수 있다면 시간이 얼마나 걸리는지 계산해보자.
Input ¶
여러 개의 테스트 케이스가 입력될 수 있다.
각 테스트 케이스의 첫째 줄에는 그리드의 크기를 나타내는 두 개의 정수 M과 N(1≤M, N≤25)이 입력된다. 그 밑으로는 M줄에 걸쳐서 각각 N개의 글자로 그리드 구성을 기술하는 내용이 입력된다. '#' 문자는 자전거가 갈 수 없는 정사각형을 나타내며, 다른 모든 정사각형에는 자전거가 갈 수 있다. 자전거의 출발지점은 'S'로, 도착지점은 'T'로 표시된다.
M과 N이 모두 0으로 입력되면 입력이 종료된다.
각 테스트 케이스의 첫째 줄에는 그리드의 크기를 나타내는 두 개의 정수 M과 N(1≤M, N≤25)이 입력된다. 그 밑으로는 M줄에 걸쳐서 각각 N개의 글자로 그리드 구성을 기술하는 내용이 입력된다. '#' 문자는 자전거가 갈 수 없는 정사각형을 나타내며, 다른 모든 정사각형에는 자전거가 갈 수 있다. 자전거의 출발지점은 'S'로, 도착지점은 'T'로 표시된다.
M과 N이 모두 0으로 입력되면 입력이 종료된다.
Output ¶
각 테스트 케이스에 대해 먼저 아래 출력 예에 나와있는 식으로 테스트 케이스 번호를 출력한다. 자전거가 도착지점에 갈 수 있으면 아래에 나와있는 형식에 맞게 초 단위로 그 지점에 가는 데 걸리는 최소 시간을 출력한다. 그렇지 않으면 "destination not reachable"이라고 출력한다.
서로 다른 테스트 케이스 사이에는 빈 줄을 하나씩 출력한다.
서로 다른 테스트 케이스 사이에는 빈 줄을 하나씩 출력한다.
Sample Input ¶
{{| 1 3
S#T
10 10
#S.......#
#..#.##.##
#.##.##.##
.#....##.#
#..#.##...
#......##.
..##.##...
#.###...#.
#.....###T
0 0 |}}
S#T
10 10
#S.......#
#..#.##.##
#.##.##.##
.#....##.#
#..#.##...
#......##.
..##.##...
#.###...#.
#.....###T
0 0 |}}
