Rätblocket

Rätblocket은 빠르게 큰 인기를 얻은 모바일 게임이다. 목표는 휴대폰을 여러 방향으로 기울여 블록을 셀 $A$에서 셀 $B$까지 굴리는 것이다. 블록의 크기는 $1$x$1$x$2$이다. 보드는 $1$x$1$ 크기의 셀로 이루어진 2차원 격자다. 어떤 셀은 자유롭게 지나갈 수 있고, 어떤 셀은 막혀 있다. 블록은 보드 밖으로 나갈 수 없다.

블록이 세워져 있는지 눕혀져 있는지에 따라 1개 또는 2개의 셀을 차지한다. 시작할 때 블록은 $A$ 표시된 셀에 세워져 있다. 목표는 블록을 $B$ 표시된 셀에 세워 두는 것이다. 블록의 절반만 $B$ 위에 걸쳐 있으면 목표를 달성한 것이 아니다. 블록은 위, 아래, 오른쪽, 왼쪽의 4가지 방향으로 움직일 수 있다. 한 번의 이동으로 블록은 주어진 방향으로 구른다. 그 방향에 막힌 셀이 있거나 보드가 끝나면 이동할 수 없다.

그림 4. 첫 번째 예시 문제 해법의 앞부분이다. 블록은 먼저 오른쪽으로 한 칸 구르고, 아래로 두 칸 구른 뒤, 마지막으로 왼쪽으로 한 칸 구른다.

보드에는 모듈로 셀이 있을 수 있다. 모듈로 셀은 $0$ 또는 $1$의 두 가지 상태를 가진다. 상태가 $0$이면 자유로운 셀처럼 동작한다. 상태가 $1$이면 솟아올라 막힌 셀처럼 동작한다. 보드에는 스위치 셀(c로 표시)도 놓여 있을 수 있다. 블록이 스위치 셀 위에 서면 모든 모듈로 셀의 상태가 바뀐다. $0$은 $1$이 되고, $1$은 $0$이 된다.

그림 5. 세 번째 예시 문제에서 스위치를 작동하기 전과 후다.

모든 보드는 유효한 해가 항상 존재하도록 설계되어 있다. 여러분의 과제는 보드를 풀기 위해 필요한 최소 이동 횟수를 구하는 것이다.

첫 줄에 두 정수 $N$과 $M$이 주어진다. 보드는 $N$개의 행과 $M$개의 열로 이루어져 있다. 이어지는 $N$개의 줄에는 각각 $M$개의 문자로 보드의 모습이 주어진다. 다음 문자가 나올 수 있다.

• $A$ 또는 $B$: 블록의 시작 위치와 도착 위치다.
• . (마침표): 자유로운 셀이다.
• #: 막힌 셀이다.
• $0$ 또는 $1$: 주어진 시작 상태를 가진 모듈로 셀이다.
• c: 스위치 셀이다.

각 보드에는 $A$가 정확히 하나, $B$가 정확히 하나 있다.

블록을 셀 $A$에서 셀 $B$까지 굴리는 데 필요한 최소 이동 횟수를 정수 하나로 한 줄에 출력한다.

배점 40점의 테스트 케이스에서 보드는 최대 $7$행 $7$열이며, 모듈로 셀은 없다. 나머지 60점의 테스트 케이스에서는 풀이가 모듈로 셀도 처리할 수 있어야 한다.