#agc043a. [agc043_a]Range Flip Find Route

[agc043_a]Range Flip Find Route

問題文

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

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

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

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

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

  • 44 つの整数 r0,c0,r1,c1(1leqr0leqr1leqH,1leqc0leqc1leqW)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) を選ぶ。r0leqrleqr1,c0leqcleqc1r_0 \\leq r \\leq r_1, c_0 \\leq c \\leq c_1 を満たす全ての r,cr, c について、(r,c)(r, c) の色を変更する。つまり、白色ならば黒色にし、黒色ならば白色にする。

制約

  • 2leqH,Wleq1002 \\leq H, W \\leq 100

入力

入力は以下の形式で標準入力から与えられる。

HH WW s11s12cdotss1Ws_{11} s_{12} \\cdots s_{1W} s21s22cdotss2Ws_{21} s_{22} \\cdots s_{2W} vdots\\vdots sH1sH2cdotssHWs_{H1} s_{H2} \\cdots s_{HW}

ここで、srcs_{rc}#. であり、#(r,c)(r, c) が黒色、. は白色であることを表す。

出力

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


入力例 1

3 3
.##
.#.
##.

出力例 1

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


入力例 2

2 2
#.
.#

出力例 2


入力例 3

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

出力例 3

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


入力例 4

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

出力例 4