Position Exchange

Time limit2sMemory limit128 MB

Summary

Find the minimum number of simultaneous turns for two players on a grid to swap starting cells, moving in 8 directions while avoiding walls, collisions, and direct swaps, using BFS over joint position states.

Level: Medium6 of 10
Topics: BFS, Graph, Matrix, Simulation
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Examples6

Example 1
Input
```
3 9
XXXXXXXXX
A.......B
XXXX.XXXX
```
Expected output
```
8
```
Example 2
Input
```
4 4
....
.A..
..B.
....
```
Expected output
```
2
```
Example 3
Input
```
3 9
XXXXXXXXX
A...X...B
XXXXXXXXX
```
Expected output
```
-1
```
Example 4
Input
```
3 9
XXXXXXXXX
A.......B
XXXXXXXXX
```
Expected output
```
-1
```

Example 5

Input

5 15
...A.XXXXX.....
.....XXXXX.....
...............
.....XXXXX.B...
.....XXXXX.....

Expected output

Example 6

Input

20 20
AB.................X
XXXXXXXXXXXXXXXXXXX.
X..................X
.XXXXXXXXXXXXXXXXXXX
X..................X
XXXXXXXXXXXXXXXXXXX.
X..................X
.XXXXXXXXXXXXXXXXXXX
X..................X
XXXXXXXXXXXXXXXXXXX.
X..................X
.XXXXXXXXXXXXXXXXXXX
X..................X
XXXXXXXXXXXXXXXXXXX.
X..................X
.XXXXXXXXXXXXXXXXXXX
X..................X
XXXXXXXXXXXXXXXXXXX.
...................X
.XXXXXXXXXXXXXXXXXXX

Expected output