/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
問題文
縦 H マス横 W マスのグリッドがあります。上から i 行目、左から j 列目のマスをマス (i,j) と表します。
最初、マス (i,j) は S_{i,j} が . のとき白マスであり、# のとき黒マスです。
あなたは最初マス (1,1) にいて、上下左右の 4 方向に隣接するいずれかのマスへ移動することができます。グリッドの外に移動することはできません。
あなたが移動すると、移動先のマスの白黒が反転します。
あなたの目的は全てのマスが白マスである状態にすることです。達成するまでに必要な最小移動回数を求めてください。
なお、制約の条件下で必ず全てのマスを白くできることが証明できます。
制約
- 1 \leq H,W \leq 4
- H\times W\geq 2
- H,W は整数である
- S_{i,j} は
.または#
入力
入力は以下の形式で標準入力から与えられる。
H W
S_{1,1}\ldots S_{1,W}
\vdots
S_{H,1}\ldots S_{H,W}
出力
答えを出力せよ。
入力例 1
4 4 .#.. .... .#.. ....
出力例 1
4
(1,1)\to(1,2)\to(2,2)\to(3,2)\to(2,2) と順に移動することで、4 回の移動により全てのマスを白くすることができます。
入力例 2
3 2 .. .. ..
出力例 2
0
最初から全てのマスが白いため、移動する必要はありません。
入力例 3
4 4 #..# #.## .... #.##
出力例 3
18
Problem Statement
There is a grid with H horizontal rows and W vertical columns. The cell in the i-th row from the top and j-th column from the left is denoted by cell (i, j).
Initially, cell (i, j) is white if S_{i,j} is ., and black if it is #.
You are initially at cell (1,1). You can move to an adjacent cell in one of the four directions: up, down, left, and right. You cannot exit the grid.
Whenever you make a move, the color of the cell you step into flips (from white to black and vice versa).
Your objective is to make all the cells white. Find the minimum number of moves required to do so.
One can prove that you can always make all the cells white under the given constraints.
Constraints
- 1 \leq H,W \leq 4
- H\times W\geq 2
- H and W are integers.
- S_{i,j} is
.or#.
Input
The input is given from Standard Input in the following format:
H W
S_{1,1}\ldots S_{1,W}
\vdots
S_{H,1}\ldots S_{H,W}
Output
Print the answer.
Sample Input 1
4 4 .#.. .... .#.. ....
Sample Output 1
4
By making four moves (1,1)\to(1,2)\to(2,2)\to(3,2)\to(2,2), you can make all the cells white.
Sample Input 2
3 2 .. .. ..
Sample Output 2
0
All the cells are initially white, so no moves are required.
Sample Input 3
4 4 #..# #.## .... #.##
Sample Output 3
18