문제
상수는 사악한 GodJail(갓재일)이 만든 미로에 갇혔습니다. 미로는 직사각형 모양으로, N행 M열의 방으로 구성됩니다. 상수는 1행 1열에 있고, N행 M열로 가고자 합니다.
각 방에는, 그 방에서 가야 하는 방향이(상, 하, 좌, 우) 적혀져 있습니다. 상수는 각 방에서 적혀진 방향으로 가야만 합니다.
하지만 이렇게 정해진 방향으로만 간다면 출구로 못 나갈 확률이 높습니다. 예를 들어 1행 1열의 방에 위로 가라고 적혀 있었다면, 그곳에는 방이 없으므로 상수는 움직일 수 없지요.
이것이 너무 가혹하다고 생각했던 GodJail은 특별히 상수가 몇 개의 방에 적힌 방향을 바꿀 수 있도록 허락했습니다. 하지만 방향을 많이 바꾸면 GodJail이 싫어하기 때문에, 방향을 바꾸는 것을 최소화해야 합니다. 방향을 최소로 바꾸어 도착점에 갈 때, 방향을 바꾸는 최소 횟수를 출력해 주세요!
입력
첫째 줄에는 각각 미로의 행의 개수 M과 열의 개수 N이 주어집니다.
다음 M개 행과 N개의 열에 문자로 된 문자열이 주어집니다. 각각 문자는 '<', '>', '^', 'v'(알파벳 v)로 이루어집니다.
각각 '이 방에서는' 왼쪽, 오른쪽, 위쪽, 아래쪽으로 가야 함을 뜻합니다.
<제약조건>
서브태스크 1 : M=3. N=3.
서브태스크 2 : M≤600. N≤600. 모든 방향은 위(‘^’) 또는 왼쪽(‘<’)입니다.
서브태스크 3 : M≤120. N≤120.
서브태스크 4 : M≤600. N≤600.
출력
방향을 최소로 바꾸는 횟수를 나타내는 수 하나를 출력합니다.
예제 #1
2 2
>v
<<
0
예제 #2
2 2
^<
<^
2
예제 #3
3 4
^^＞＜
＞v＜v
＞＜^^
3
힌트
출처
cki86201
로그인해야 코드를 작성할 수 있어요.