分数: 400 点
问题陈述
考虑一个网格 H 行和 W 方格列。让 (r, c) 表示位于 r从顶部算起的第行和 c左起第 列。 每个方块都漆成黑色或白色。
网格据说是 好 当且仅当满足以下条件时:
- 来自 (1, 1),我们可以到达 (H, W) 移动一格 向右或向下 重复 ,同时始终位于白色方块上。 如果网格良好,
请注意 (1, 1) 和 (H, W) 必须是白色。
你的任务是通过重复以下操作来使网格良好。找出完成任务所需的最少操作数。可以证明,你总是可以在有限次数的操作中完成任务。
- 选择四个整数 r_0, c_0, r_1, c_1(1 \leq r_0 \leq r_1 \leq H, 1 \leq c_0 \leq c_1 \leq W)。对于每对 r, c (r_0 \leq r \leq r_1, c_0 \leq c \leq c_1),反转颜色 (r, c) - 即从白色到黑色,反之亦然。
约束
- 2 \leq H, W \leq 100
输入
输入由标准输入按以下格式给出:
H W
s_{11} s_{12} \cdots s_{1W}
s_{21} s_{22} \cdots s_{2W}
\vdots
s_{H1} s_{H2} \cdots s_{HW}
这里 s_{rc} 代表颜色 (r, c) - # 代表黑色,并且 . 代表白色。
输出
打印所需的最少操作数。
示例输入 1
3 3 .## .#. ##.
示例输出 1
1
进行操作 (r_0, c_0, r_1, c_1) = (2, 2, 2, 2) 仅更改颜色 (2, 2),我们就完成了。
示例输入 2
2 2 #. .#
示例输出 2
2
示例输入 3
4 4 ..## #... ###. ###.
示例输出 3
0
可能不需要任何操作。
示例输入 4
5 5 .#.#. #.#.# .#.#. #.#.# .#.#.
示例输出 4
4