问题陈述
有一个网格 H 水平行和 W 垂直列。该单元格位于 i从顶部开始的第行和 j从左边算起的第列由单元格表示 (i, j).
最初,细胞 (i, j) 为白色,如果 S_{i,j} is .,如果是黑色 #.
您最初位于牢房 (1,1)。您可以沿四个方向之一移动到相邻单元格:上、下、左、右。您无法退出网格。
每当您移动时,您进入的单元格的颜色就会翻转(从白色变为黑色,反之亦然)。
您的目标是使所有单元格变白。求出这样做所需的最少移动次数。
可以证明,在给定的约束下,您始终可以将所有单元格设置为白色。
约束
- 1 \leq H,W \leq 4
- H\times W\geq 2
- H 和 W 是整数。
- S_{i,j} is
.or#.
输入
输入由标准输入按以下格式给出:
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),可以将所有单元格设置为白色。
示例输入 2
3 2 .. .. ..
示例输出 2
0
所有单元格最初都是白色的,因此不需要移动。
示例输入 3
4 4 #..# #.## .... #.##
示例输出 3
18