1473번 - 미로 탈출

세준이는 직사각형 모양의 미로에 갇혔다. 미로 안에는 1*1크기의 작은 방이 있다. 정사각형 모양의 각 방은 네 개의 면이 있는데, 이 네 개의 면에는 문이 있을수도 있고, 없을수도 있다. 각 방은 네 개의 타입이 있는데, A는 네 면 모두 문이 있는 것이고, B는 문이 없는 것, C는 문이 위쪽, 아래쪽에만 있는 것, D는 문이 왼쪽, 오른쪽에만 있는 것이다.

세준이는 미로를 문을 통해서 방에서 방으로 자유롭게 이동할 수 있다. 그러나, 세준이가 방 X에서 방 Y로 가려고 한다면, 방 X에도 문이 있고, 방 Y에도 문이 있어야 한다. 예를 들어, 세준이가 현재 있는 방에 문이 위쪽에 있고, 위쪽 방에 문이 아래쪽에 있으면, 세준이는 위쪽 방으로 이동할 수 있다. 만약 위쪽 방에 아래쪽으로 향하는 문이 없다면 세준이는 위쪽 방으로 갈 수 없다.

미로는 정말 단단한 벽으로 둘러쌓여 있어서, 문이 있더라도 밖으로 나갈 수 없다. 어떤 방에서 어떤 방으로 움직일 때는 1초가 걸린다.

미로에는 세준이가 자유롭게 이동할 만큼 문이 충분하지 않을 수도 있다. 따라서, 세준이는 미로를 조정할 수 있는 버튼이 있다. 이 버튼을 누르게 되면, 세준이가 현재 있는 모든 행의 방이 90도만큼 회전하고, 세준이가 현재 있는 모든 열의 방이 90도만큼 회전한다. 따라서, 세준이가 있던 방은 90도만큼 두 번 회전하기 때문에, 그대로일 것이다. 만약 어떤 방에 위쪽 문이 있었으면, 90도 회전을 해서 오른쪽 문으로 바꿀 수 있다.

버튼을 눌러서 방의 모양이 바뀌는 시간도 1초이다.

미로의 가장 위쪽에서 왼쪽에 있는 세준이가, 가장 아래쪽에서 오른쪽으로 이동하려고 할 때, 드는 시간의 최솟값을 출력하는 프로그램을 작성하시오.

첫째 줄에 미로의 세로 크기 N과 미로의 가로 크기 M이 주어진다. N과 M은 2보다 크거나 같고, 7보다 작거나 같은 자연수이다. 둘째 줄에 미로의 정보가 들어온다. 미로의 정보는 ABCD 네 개의 문자로만 이루어져 있다.

첫째 줄에 세준이가 이동하는 시간의 최솟값을 출력하시오. 만약 이동할 수 없으면 -1을 출력한다.