몸짱 무길이의 취미는 암벽 등반이다.

실내 암벽 등반이 너무 지겨웠던 무길이는 바위 절벽을 오르기로 했다.

그런데 모든 절벽이 실내 체육관처럼 오르기 좋게 만들어진 것은 아니다.

무길이는 다행히도 프로그래머이기도 하기 때문에, 절벽 분석용 앱을 가지고있다.

이 앱은 절벽을 격자의 형태로 분석하여, 각 위치의 암석이 어떤 지반의 암석인지 알려준다.

앱의 설명서에 따르면, F는 발을 디딜 수 있는 암석이며, H는 손으로 잡을 수 있는 암석이다.

발도 디딜 수 있고, 손으로도 잡을 수 있는 암석은 B로 표시되며, 둘 다 불가능한 경우는 X로 표시된다.

무길이의 위치는 *로 표시되며, B와 마찬가지로 손과 발을 모두 사용 가능한 곳이다.

암벽 등반을 하는 방법은 다음과 같다.

*가 표시된 곳에 무길이의 손과 발이 모두 위치한 상태로 시작한다.

무길이 키가 199cm나 되긴 하지만, 각 칸은 2m 정도 떨어져 있기 때문에, 등반 과정 중 어떤 경우에도 무길이의 손과 발은 1칸 이상 차이가 날 수 없다.

(이 때 한 칸의 의미는 대각선 방향을 포함한다.)

또한, 무길이는 거꾸로 매달려 있을 수 없기 때문에, 발의 위치가 손의 위치보다 높을 수는 없다.

예를 들어, 무길이의 발이 [3,3] 에 위치해있다면, 손은 [2,2] [2,3] [2,4] [3,2] [3,3] [3,4] 6가지 위치에 있을 수 있다.

손이 [3,3]에 위치해있다면, 발은 [3,2][3,3][3,4][4,2][4,3][4,4] 6가지 위치에 있을 수 있다.

또한 무길이는 톰 크루즈가 아니기 때문에 한번의 이동으로 손이나 발 둘 중 하나만 이동할 수 있다.

(톰 크루즈는 영화 미션 임파서블 2에서, 무려 안전장비 없이 손과 발을 동시에 떼서 절벽에서 점프하여 다른 암벽에 착지하는 모습을 촬영하였다.)

무길이가 *에서 시작하여, 제일 높은 곳에 발을 올릴 수 있으면, 그 암벽을 등반 가능하다고 한다.

암벽의 상태가 주어졌을 때, 그 암벽이 등반 가능한지 아닌지 알아내는 프로그램을 작성하라.

암벽 등반 timer 1s memory 512MB

암벽 등반 1s 512MB