题目描述

$H$ 行 $W$ 列のマス目を考えます。上から $r$ 番目、左から $c$ 番目のマスを $(r,\ c)$ と表すことにします。 全てのマスはそれぞれ白か黒のどちらかの色に塗られています。

次のような経路が存在するとき、このマス目を"良い"状態と呼びます。

• 常に白いマスの上にいながら、$(1,\ 1)$ から、一つ 右か下 のマスに移動することを繰り返し、 $(H,\ W)$ へ移動する。

ここで、"良い"状態ならば $(1,\ 1)$ や $(H,\ W)$ が必ず白いことに注意してください。

あなたの仕事は、以下の操作を繰り返し、マス目を"良い"状態にすることです。最小で何回操作を行う必要があるか求めてください。なお、有限回の操作で必ず"良い"状態に出来ることが証明可能です。

• $4$ つの整数 $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$ について、$(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)$ が黒色、. は白色であることを表す。

输出格式

最小の操作回数を出力せよ。

题目大意

给出只包含.和#的 $H \times W$ 网格，每次操作指定 $r_0,\ c_0,\ r_1,\ c_1\ (1 \le r_0 \le r_1 \le H,\ 1 \le c_0 \le c_1 \le L)$，使 $(r,\ c)\ (r_0 \le r \le r_1,\ c_0 \le c \le c_1)$ 的.变#，#变.。

操作结束后，有一条从 $(1,\ 1)$ 到 $(H,\ W)$ 的路径，满足：

• 只向右或向下移动。
• 只经过.。

求最小操作数。

3 3
.##
.#.
##.

1

2 2
#.
.#

2

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

0

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

4

提示

制約

• $2\ \leq\ H,\ W\ \leq\ 100$

Sample Explanation 1

$(r_0,\ c_0,\ r_1,\ c_1)\ =\ (2,\ 2,\ 2,\ 2)$、つまりマス $(2,\ 2)$ のみ色を変更すれば良いです。

Sample Explanation 3

操作が必要ない場合も存在します。