/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 150 点
問題文
縦 H マス横 W マスのグリッドのいくつかのマスにヤギがいる。 ふわりは、ヤギのいないいくつかのマスに柵を設置して、どのヤギも、移動をくりかえしてグリッドの外に出ることができないようにしたい。 ヤギは上下左右の隣接する柵のないマスに移動することができる。 ヤギがグリッドの端の行や列にいるときは、グリッドの外に移動することができる。 柵の設置が終わるまでヤギは動かないとする。 目的を達成するのに必要な柵の最小個数を求めよ。
制約
- 1 \leq H \leq 100
- 1 \leq W \leq 100
- グリッドの少なくとも 1 マスにはヤギが存在する。
入力
入力は以下の形式で標準入力から与えられる。
H W S_1 : S_H
S_i (1 \leq i \leq H) の j (1 \leq j \leq W) 文字目はグリッドの上から i 行目、左から j 列目の状態を表す。
. のとき、このマスには何もないことを表す。
X のとき、このマスにヤギがいることを表す。
出力
設置する必要のある柵の最小個数を一行で出力せよ。いくつ柵を設置してもグリッドの外に出ることができるヤギが存在するときは -1 を出力せよ。
入力例1
4 5 ..... ..... ..X.. .....
出力例1
4
3 行目の 2 列目と 2 行目の 3 列目と 3 行目の 4 列目と 4 行目の 3 列目に設置すればよい。
入力例2
2 2 .. .X
出力例2
-1
この例ではどのようにしてもヤギはグリッドの外へ出ることができる。
入力例3
6 6 ...... ...... ..X... .X..X. ..X... ......
出力例3
10
Score : 150 points
Problem Statement
There are some goats on a grid with H rows and W columns. Alice wants to put some fences at some cells where goats do not exist so that no goat can get outside the grid. Goats can move in the four directions, that is, up, down, right and left. Goats can not move onto the cells where fences are placed. If a goat exists at one of the outermost cells in the grid, it can move outside. Goats do not move until all fences are placed. Find the minimum number of fences to be placed.
Constraints
- 1 \leq H \leq 100
- 1 \leq W \leq 100
- There is at least one goat on the given grid.
Input
The input is given from the Standart Input in the following format:
H W S_1 : S_H
The j-th (1 \leq j \leq W) character in S_i (1 \leq i \leq H) represents
whether a goat exists at the cell located at row i and column j.
Character . represents there is no goat, and X represents there is one goat at the cell.
Output
Print the minimun number of fences to be placed. If there is no way to keep all the goats inside the grid, print -1.
Sample Input 1
4 5 ..... ..... ..X.. .....
Sample Output 1
4
The optimum answer is to put fences at the cells located at row 3 and column 2, row 2 and column 3, row 3 and column 4, and row 4 and column 3.
Sample Input 2
2 2 .. .X
Sample Output 2
-1
In this case, there is no way to keep the goats inside the grid.
Sample Input 3
6 6 ...... ...... ..X... .X..X. ..X... ......
Sample Output 3
10