Moving Pieces

Interview

Time limit2sMemory limit512 MB

Summary

Given at most 5 pieces on a 5x5 board, find the minimum number of sliding moves so all pieces form one connected component.

Level: Medium7 of 10
Topics: BFS, Brute force, Graph, Implementation
Solved: No attempts yet

Problem

There is a 5×5 board with at most 5 pieces on it. You want to move the pieces so that all of them form a single connected component. That is, when you connect pieces that are adjacent horizontally or vertically, every pair of pieces must be linked through at least one path.

In one move, you may shift a single piece to an adjacent cell in one of the four directions (up, down, left, right). Because each cell can hold at most one piece, you cannot move a piece onto a cell that is already occupied. Given the state of the board, write a program that finds the minimum number of moves needed to make all pieces form a single connected component.

Input

The state of the board is given over five lines. An empty cell is denoted by ., and a piece by *. The number of pieces is between 1 and 5, inclusive.

Output

Print the minimum number of moves required to make all pieces form a single connected component.

Examples3

Example 1
Input
```
*...*
.....
.....
.....
*...*
```
Expected output
```
12
```
Example 2
Input
```
.....
..**.
.....
...*.
.....
```
Expected output
```
1
```
Example 3
Input
```
.....
.....
.**..
.*...
**...
```
Expected output
```
0
```