AT_agc043_a [AGC043A] Range Flip Find Route

[problemUrl]: https://atcoder.jp/contests/agc043/tasks/agc043_a $ 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) $ が黒色、`.` は白色であることを表す。

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

### 制約 - $ 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 操作が必要ない場合も存在します。