위치 교환

빈칸, 벽, 두 플레이어 A와 B의 시작 위치가 표시된 게임판이 주어진다. A와 B가 서로의 시작 위치를 바꾸는 데 필요한 최소 턴 수를 구하시오.

한 턴에는 A와 B 중 한 명 또는 두 명이 움직일 수 있다. 한 번 움직일 때는 현재 칸에서 위, 아래, 왼쪽, 오른쪽, 또는 네 대각선 방향 중 하나로 한 칸 이동한다. 벽으로 이동하거나 게임판 밖으로 나갈 수는 없다.

각 턴이 끝났을 때 두 플레이어가 같은 칸에 있어서는 안 된다. 또한 한 턴 동안 두 플레이어가 서로의 위치를 직접 맞바꾸는 이동은 할 수 없다.

예를 들어 A가 어떤 칸에 있고 B가 바로 오른쪽 칸에 있을 때, B가 왼쪽으로 이동한다면 A는 동시에 오른쪽으로 이동할 수 없다. 이것은 서로의 위치를 직접 맞바꾸는 이동이기 때문이다. 반대로 B가 왼쪽이 아닌 다른 방향으로 이동한다면 A는 오른쪽으로 이동할 수 있다.

A가 (0, 0), B가 (0, 1)에 있을 때 A가 오른쪽 아래 대각선으로, B가 왼쪽 아래 대각선으로 이동하면 두 이동 선분은 (0.5, 0.5)에서 만나지만, 서로의 위치를 직접 맞바꾸는 것이 아니므로 허용된다.

첫째 줄에 게임판의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 20 이하의 자연수이다.

둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 빈칸은 ., 벽은 X, A의 위치는 A, B의 위치는 B로 표시된다.

A와 B가 서로의 시작 위치를 바꾸는 데 필요한 최소 턴 수를 출력한다. 바꿀 수 없다면 -1을 출력한다.