Position Exchange

You are given a game board containing empty cells, walls, and the starting positions of two players A and B. Find the minimum number of turns needed for A and B to exchange their starting positions.

In one turn, one or both players may move. A move sends a player by one cell in one of the eight directions: up, down, left, right, or one of the four diagonals. A player cannot move into a wall or outside the board.

After each turn, the two players must not occupy the same cell. Also, during a single turn, the players are not allowed to directly swap their current positions.

For example, suppose A is on a cell and B is immediately to its right. If B moves left, then A cannot move right in the same turn, because that would directly swap their positions. If B moves in any other direction, A may move right.

If A is at (0, 0) and B is at (0, 1), and A moves diagonally down-right while B moves diagonally down-left, their movement segments meet at (0.5, 0.5). This is allowed because they do not directly swap positions.

The first line contains the board height N and width M. Both N and M are positive integers no greater than 20.

Each of the next N lines describes the board. An empty cell is written as ., a wall as X, A's position as A, and B's position as B.

Print the minimum number of turns needed for A and B to exchange their starting positions. If it is impossible, print -1.