미샤는 무선 조종 자동차를 이용해 레이스를 진행하려고 한다. 규칙은 간단하다. $n \times m$ 의 격자 형태의 미로가 주어지고, 레이스의 시작 지점과 도착 지점이 정해지면, 자동차를 시작 지점에 둔 후 조종을 해 도착 지점까지 이동시키면 된다.
미샤의 자동차는 이동하는 방식이 조금 특이한데, 자동차를 움직이기 위해 조종기의 상하좌우 방향키 중 하나를 누르면, 누른 방향키에 해당하는 방향으로 장애물을 만나거나 미로의 끝부분에 도달할 때까지 이동한 후, 이동한 거리의 절반을 버림한 거리만큼 반대 방향으로 튕겨져 나간다. 즉, 자동차가 튕겨져 나가기 전 $k$ 칸을 이동했다면, $\lfloor\;k\;/\;2\;\rfloor$ 칸만큼 반대 방향으로 다시 이동하게 되는 것이다.
미샤는 이 레이스에서 우승하고 싶다. 그렇기에 조종기의 방향키를 누르는 횟수를 최소한으로 하고 싶다. 미샤를 위해 여러분이 도착 지점으로 자동차를 이동시키기 위한 최소 횟수를 구해 주자. 단, 방향키 여러 개를 동시에 누를 수는 없으며, 자동차가 이동을 완료해 정지할 때까지 방향키를 누를 수 없다. 또한 이동 중이거나 튕겨져 나가는 과정에서 도착 지점을 지나친 것은 도착 지점에 도착한 것으로 인정하지 않는다.
입력
첫 번째 줄에 $n, m\;(2 \le n, m \le 20)$ 이 공백 한 칸을 사이에 두고 차례대로 주어진다.
이후 $n$ 개의 줄에 걸쳐 미로의 형태가 공백 없이 붙어서 주어진다. S 는 시작 지점, T 는 도착 지점, # 는 장애물, . 는 빈 칸을 의미한다. S 와 T 는 정확히 한 번만 주어진다.
출력
첫 번째 줄에 자동차가 도착 지점에 도착하기 위해 눌러야 하는 방향키의 최소 횟수를 출력한다. 만약 어떻게 자동차를 조종하더라도 도착 지점에 도착하는 것이 불가능하다면, -1 를 출력한다.
wizardrabbit 3년 전 8
* 본 지문은 21416번 문제를 번역 및 재구성하여 작성했습니다.
문제
미샤는 무선 조종 자동차를 이용해 레이스를 진행하려고 한다. 규칙은 간단하다. $n \times m$ 의 격자 형태의 미로가 주어지고, 레이스의 시작 지점과 도착 지점이 정해지면, 자동차를 시작 지점에 둔 후 조종을 해 도착 지점까지 이동시키면 된다.
미샤의 자동차는 이동하는 방식이 조금 특이한데, 자동차를 움직이기 위해 조종기의 상하좌우 방향키 중 하나를 누르면, 누른 방향키에 해당하는 방향으로 장애물을 만나거나 미로의 끝부분에 도달할 때까지 이동한 후, 이동한 거리의 절반을 버림한 거리만큼 반대 방향으로 튕겨져 나간다. 즉, 자동차가 튕겨져 나가기 전 $k$ 칸을 이동했다면, $\lfloor\;k\;/\;2\;\rfloor$ 칸만큼 반대 방향으로 다시 이동하게 되는 것이다.
미샤는 이 레이스에서 우승하고 싶다. 그렇기에 조종기의 방향키를 누르는 횟수를 최소한으로 하고 싶다. 미샤를 위해 여러분이 도착 지점으로 자동차를 이동시키기 위한 최소 횟수를 구해 주자. 단, 방향키 여러 개를 동시에 누를 수는 없으며, 자동차가 이동을 완료해 정지할 때까지 방향키를 누를 수 없다. 또한 이동 중이거나 튕겨져 나가는 과정에서 도착 지점을 지나친 것은 도착 지점에 도착한 것으로 인정하지 않는다.
입력
첫 번째 줄에 $n, m\;(2 \le n, m \le 20)$ 이 공백 한 칸을 사이에 두고 차례대로 주어진다.
이후 $n$ 개의 줄에 걸쳐 미로의 형태가 공백 없이 붙어서 주어진다.
S는 시작 지점,T는 도착 지점,#는 장애물,.는 빈 칸을 의미한다.S와T는 정확히 한 번만 주어진다.출력
첫 번째 줄에 자동차가 도착 지점에 도착하기 위해 눌러야 하는 방향키의 최소 횟수를 출력한다. 만약 어떻게 자동차를 조종하더라도 도착 지점에 도착하는 것이 불가능하다면,
-1를 출력한다.힌트