Two Coins

Interview

Time limit2sMemory limit512 MB

Summary

Move both coins together with four direction buttons and find the shortest press sequence that drops exactly one coin off the board.

Level: Medium5 of 10
Topics: BFS, Graph, Matrix, Implementation
Solved: No attempts yet

Problem

There is a game played on an N×M board with four buttons. The board is divided into 1×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". Pressing a button moves both coins simultaneously in the direction written on the button.

If the cell a coin wants to move into is a wall, the coin does not move.
If there is no cell in the direction a coin wants to move, the coin falls off the board.
Otherwise, the coin moves one cell in that direction. It also moves one cell when the target cell 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 ≤ N, M ≤ 20)

The next N lines give the state of the board.

o: a coin
.: an empty cell
#: a 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 the coins fall off, or if more than 10 presses are needed, 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
```