题目描述

我们有一个 $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)$ 是白色。

输出格式

输出最少的操作次数。

样例 1

输入

3 3
.##
.#.
##.

输出

1

样例 2

输入

2 2
#.
.#

输出

2

样例 3

输入

4 4
..##
#...
###.
###.

输出

0

样例 4

输入

5 5
.#.#.
#.#.#
.#.#.
#.#.#
.#.#.

输出

4

说明/提示

限制

• $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 翻译