상수는 사악한 GodJail(갓재일)이 만든 미로에 갇혔습니다. 미로는 직사각형 모양으로, N행 M열의 방으로 구성됩니다. 상수는 1행 1열에 있고, N행 M열로 가고자 합니다.

각 방에는, 그 방에서 가야 하는 방향이(상, 하, 좌, 우) 적혀져 있습니다. 상수는 각 방에서 적혀진 방향으로 가야만 합니다.

하지만 이렇게 정해진 방향으로만 간다면 출구로 못 나갈 확률이 높습니다. 예를 들어 1행 1열의 방에 위로 가라고 적혀 있었다면, 그곳에는 방이 없으므로 상수는 움직일 수 없지요.

이것이 너무 가혹하다고 생각했던 GodJail은 특별히 상수가 몇 개의 방에 적힌 방향을 바꿀 수 있도록 허락했습니다. 하지만 방향을 많이 바꾸면 GodJail이 싫어하기 때문에, 방향을 바꾸는 것을 최소화해야 합니다. 방향을 최소로 바꾸어 도착점에 갈 때, 방향을 바꾸는 최소 횟수를 출력해 주세요!

#2701 upload 103 done 18 how_to_reg 14

미로 timer 1s memory 64MB

#2701

미로 1s 64MB