← 返回题目列表

AtCoder · past18_j

J. 逆转游戏

中文机器翻译题面 查看原题

问题陈述

有一个网格 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