Hypertheseus

어느 광고 회사는 프로메테우스, 아킬레우스, 오디세우스 같은 고대 영웅들을 소재로 한 광고를 만들기 위해, 각 영웅이 겪은 가장 유명한 시련을 컴퓨터로 시뮬레이션한다. 이 문제에서는 그중 테세우스의 이야기를 다룬다.

테세우스는 빠져나올 수 없는 미궁(Labyrinth) 속에 사는 반인반수 괴물 미노타우로스를 처치한 아테네의 영웅이다. 그의 진짜 시련은 괴물을 쓰러뜨리는 것이 아니라, 미궁에서 빠져나올 길을 찾는 것이었다. 여기서는 그 과제를 다음 규칙에 따라 시뮬레이션한다.

• 미궁은 $d$차원 격자이며, 크기는 $n_1 \times n_2 \times \cdots \times n_d$개의 (초)입방체로 이루어진다. 각 입방체는 빈 칸(통로) 이거나 바위(벽) 이다.
• 테세우스는 한 걸음에 인접한 두 빈 입방체 사이를 이동한다. 두 입방체는 정확히 한 차원에서 좌표가 1만큼 차이 나고, 나머지 모든 차원에서 좌표가 같을 때만 서로 인접한 것으로 본다.
• 테세우스는 맨손으로 미노타우로스를 이길 수 없으므로, 미궁 어딘가에 놓인 검을 먼저 손에 넣어야 한다. 검을 얻기 전에는 미노타우로스가 있는 입방체를 지나갈 수 없다.

입력은 여러 개의 미궁 설명으로 이루어진다. 각 미궁 설명은 다음과 같다.

• 첫 줄: 차원 수를 나타내는 정수 $d$ ($2 \le d \le 20$).
• 둘째 줄: 공백으로 구분된 $d$개의 정수 $n_1, n_2, \ldots, n_d$. 각 차원에서 미궁의 크기를 단위 입방체 수로 나타내며, 모든 $i$에 대해 $n_i \ge 2$이다. 한 미궁의 전체 입방체 수는 $2^{20} = 1048576$을 넘지 않는다.
• 이어서 미궁 지도가 재귀적으로 주어진다.
  • 2차원 미궁(크기 $n_1 \times n_2$)은 각 줄에 $n_1$개의 문자가 있는 $n_2$개의 줄로 표현한다. 각 문자는 입방체 하나를 나타내며, #(바위), .(빈 칸), 또는 대문자 T(테세우스의 위치), M(미노타우로스), S(검) 중 하나이다. T, M, S는 미궁 전체에서 각각 정확히 한 번씩 나타나며, 이 세 칸은 모두 빈 칸으로 간주되어 지나갈 수 있다.
  • 각 2차원 지도 뒤에는 빈 줄이 하나 온다.
  • $d > 2$인 경우, $d$차원 미궁은 $n_d$개의 "층"이 이어진 것이며, 각 층은 하나의 $(d-1)$차원 미궁 설명이다.

마지막 미궁 설명 뒤에는 0 하나만 있는 줄이 오며, 이 줄은 입력의 끝을 나타낸다. 이 줄에 대해서는 아무것도 출력하지 않는다.

각 미궁에 대해 다음 한 줄을 출력한다.

Theseus needs S steps.

여기서 $S$는 테세우스가 자신의 시작 칸에서 출발하여 검이 있는 칸에 도달하고, 이어서 미노타우로스가 있는 칸에 도달한 뒤, 다시 자신의 시작 칸(출구가 있다고 가정하는 위치)으로 돌아오기까지 필요한 최소 걸음 수이다. 미궁 밖으로는 나갈 수 없으며, 미궁 영역 바깥의 모든 입방체는 바위로 간주한다. 출구는 내부 입방체에 있을 수 있고, 반드시 "경계"에 있을 필요는 없다.

상황을 전혀 해결할 수 없는 경우에는 다음을 출력한다.

No solution. Poor Theseus!