配点 : $400$ 点

問題文

$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)$ の色を変更する。つまり、白色ならば黒色にし、黒色ならば白色にする。

制約

• $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)$ が黒色、. は白色であることを表す。

出力

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

3 3
.##
.#.
##.

1

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

2 2
#.
.#

2

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

0

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

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

4