AT_agc043_a [AGC043A] Range Flip Find Route

我们有一个 $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_0 \leq r \leq r_1,\ c_0 \leq c \leq c_1$ 的格子 $(r, c)$，将其颜色反转（白变黑，黑变白）。

输入通过标准输入给出，格式如下： > $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)$ 是黑色，`.` 表示 $(r, c)$ 是白色。

输出最少的操作次数。

## 限制 - $2 \leq H, W \leq 100$ ## 样例解释 1 只需对 $(r_0, c_0, r_1, c_1) = (2, 2, 2, 2)$，即只改变格子 $(2, 2)$ 的颜色即可。 ## 样例解释 3 有些情况下不需要进行任何操作。 由 ChatGPT 4.1 翻译