Two Coins Unlimited

Interview

Time limit0.5sMemory limit512 MB

Summary

Two coins sit on a grid with walls; each button press slides both coins the same direction, and you must find the fewest presses that drop exactly one coin off the board.

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

Problem

There is a game played on an $N \times M$ board with 4 buttons. The board is divided into $1 \times 1$ square cells, and each cell is either empty or a wall. Two empty cells each contain one coin, and the two coins are in different positions.

The four buttons are "left", "right", "up", and "down". When a button is pressed, both coins move at the same time in the direction written on the button.

If the cell a coin would move into is a wall, the coin does not move.
If there is no cell in the direction a coin would move, the coin falls off the board.
Otherwise, the coin moves one cell in that direction. It also moves one cell when the cell it would move into contains a coin.

Write a program that finds the minimum number of button presses needed to make exactly one of the two coins fall off the board.

Input

The first line gives the board's height $N$ and width $M$ . ( $1 \le N, M \le 20$ )

The next $N$ lines give the state of the board.

o: coin
.: empty cell
#: wall

The number of coins is always 2.

Output

On the first line, print the minimum number of button presses needed to make exactly one of the two coins fall off the board. If it is impossible to make a coin fall off, print -1.

Examples5

Example 1
Input
```
1 2
oo
```
Expected output
```
1
```
Example 2
Input
```
6 2
.#
.#
.#
o#
o#
##
```
Expected output
```
4
```
Example 3
Input
```
6 2
..
..
..
o#
o#
##
```
Expected output
```
3
```
Example 4
Input
```
5 3
###
.o.
###
.o.
###
```
Expected output
```
-1
```
Example 5
Input
```
5 3
###
.o.
#.#
.o.
###
```
Expected output
```
3
```