Minimal Steps for Defensive Deployment

Our intelligence has intercepted enemy plans: they are massing troops to attack our vital military research facility. The facility’s layout is represented as an \(N \times M\) grid. Each cell in the grid is one of three types:

• O — a research area used for military studies.
• # — a cell currently occupied by a mechanized battalion.
• . — an empty area.

Note that no cell may house more than one battalion. Due to spatial constraints, in the final deployment the battalions cannot remain on research areas. However, during their repositioning they may pass through them.

The command’s objective is to reposition the battalions using the minimum total number of unit moves so that every research area is surrounded. Here, a research area is considered surrounded if, after deployment, an enemy infiltrating from any border cell cannot reach any research area without encountering a cell occupied by a battalion. In other words, if one performs a flood fill from all border cells (ignoring battalion-occupied cells), no research area should be reachable.

Movement rules are as follows: In each unit time, the command may instruct exactly one battalion to move one step (up, down, left, or right) into an adjacent cell, provided the cell is within bounds and unoccupied by another battalion. In the final arrangement, battalions must not reside on research areas.

Your task is to compute the minimum number of moves required to achieve such a deployment. If it is impossible, output -1.

Note: The grid size will be small (e.g. \(N, M \leq 10\)), so a state-space search solution is acceptable.

inputFormat

The first line of input contains two integers \(N\) and \(M\) (\(1 \leq N, M \leq 10\)) representing the number of rows and columns in the grid. The following \(N\) lines each contain a string of \(M\) characters. Each character is either:

• O for a research area,
• # for a cell occupied by a battalion, or
• . for an empty area.

outputFormat

Output a single integer representing the minimum total number of moves required to reposition the battalions so that every research area is surrounded as described. If it is impossible to achieve such a deployment, output -1.

sample

3 3
#.#
.O.
#.#

4