미로 탈출

세준이는 직사각형 미로의 왼쪽 위 방에서 시작해 오른쪽 아래 방으로 가려고 한다. 미로는 1 x 1 크기의 방들로 이루어져 있고, 각 방의 네 면에는 문이 있을 수도 있고 없을 수도 있다.

방의 종류는 네 가지이다.

• A: 네 방향 모두에 문이 있다.
• B: 문이 없다.
• C: 위쪽과 아래쪽에만 문이 있다.
• D: 왼쪽과 오른쪽에만 문이 있다.

인접한 두 방 사이를 이동하려면 양쪽에 모두 문이 있어야 한다. 즉, 현재 방에는 이동하려는 방향의 문이 있어야 하고, 도착할 방에는 그 반대 방향의 문이 있어야 한다. 예를 들어 위쪽으로 이동하려면 현재 방에 위쪽 문이 있고, 위쪽 방에는 아래쪽 문이 있어야 한다.

미로의 바깥쪽은 단단한 벽으로 둘러싸여 있으므로, 바깥쪽을 향한 문이 있더라도 미로 밖으로 나갈 수 없다. 인접한 방으로 한 번 이동하는 데에는 1초가 걸린다.

처음 상태의 미로에는 세준이가 목적지까지 이동하기에 충분한 문이 없을 수도 있다. 세준이는 미로를 조정하는 버튼을 가지고 있다. 버튼을 누르면 세준이가 있는 행의 모든 방이 90도 회전하고, 세준이가 있는 열의 모든 방도 90도 회전한다. 세준이가 서 있는 방은 그 행과 열에 모두 포함되므로 두 번 회전하여 모양이 그대로 유지된다. 90도 회전하면 위쪽 문은 오른쪽 문이 된다.

버튼을 누르는 데에도 1초가 걸린다.

왼쪽 위 방에서 오른쪽 아래 방까지 이동하는 데 필요한 최소 시간을 구하시오.

첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 각각 2 이상 7 이하의 정수이다.

다음 N개 줄에는 미로의 각 행을 나타내는 길이 M의 문자열이 주어진다. 각 문자는 A, B, C, D 중 하나이다.

세준이가 목적지까지 이동하는 데 필요한 최소 시간을 출력한다. 이동할 수 없다면 -1을 출력한다.