問題文
H 行 W 列のマス目を考えます。上から r 番目、左から c 番目のマスを (r,c) と表すことにします。 全てのマスはそれぞれ白か黒のどちらかの色に塗られています。
次のような経路が存在するとき、このマス目を"良い"状態と呼びます。
- 常に白いマスの上にいながら、(1,1) から、一つ 右か下 のマスに移動することを繰り返し、 (H,W) へ移動する。
ここで、"良い"状態ならば (1,1) や (H,W) が必ず白いことに注意してください。
あなたの仕事は、以下の操作を繰り返し、マス目を"良い"状態にすることです。最小で何回操作を行う必要があるか求めてください。なお、有限回の操作で必ず"良い"状態に出来ることが証明可能です。
- 4 つの整数 r0,c0,r1,c1(1leqr0leqr1leqH,1leqc0leqc1leqW) を選ぶ。r0leqrleqr1,c0leqcleqc1 を満たす全ての r,c について、(r,c) の色を変更する。つまり、白色ならば黒色にし、黒色ならば白色にする。
制約
- 2leqH,Wleq100
入力
入力は以下の形式で標準入力から与えられる。
H W
s11s12cdotss1W
s21s22cdotss2W
vdots
sH1sH2cdotssHW
ここで、src は #
か .
であり、#
は (r,c) が黒色、.
は白色であることを表す。
出力
最小の操作回数を出力せよ。
入力例 1
出力例 1
(r0,c0,r1,c1)=(2,2,2,2)、つまりマス (2,2) のみ色を変更すれば良いです。
入力例 2
出力例 2
入力例 3
出力例 3
操作が必要ない場合も存在します。
入力例 4
出力例 4