F - Stamps 1 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 100 点

Stamps 1 ~ 4 において，スタンプの種類と制約以外の問題設定は共通しています．

問題文

うさぎは H \times W の長方形のマス目を持っている． マス目の上から i 行目 (1 \le i \le H)，左から j 列目 (1 \le j \le W) のマスをマス (i,j) と呼ぶ．

マス (i,j) の初期状態は文字 S_{i,j} で表され，# は黒く塗られていること，. は塗られていないことを意味する．

うさぎはクリスマスプレゼントとしてスタンプをもらった．

このスタンプを 1 回押すと縦 H/2 マス横 W/2 マスの大きさの長方形を黒く塗りつぶすことができる． すなわち，整数 i_0,j_0 を選んだとき，i_0 \le i \lt i_0+H/2 かつ j_0 \le j \lt j_0+W/2 を満たすようなマス (i,j) を全て黒く塗ることができる．

うさぎはこのスタンプを使って全てのマスを黒く塗ろうとしている． 最小で何回スタンプを押せば良いだろうか？

制約

  • 2 \le H,W \le 1000
  • H,W はいずれも偶数
  • S_{i,j} は . または #

入力

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

H W
S_{1,1}S_{1,2}...S_{1,W}
S_{2,1}S_{2,2}...S_{2,W}
:
S_{H,1}S_{H,2}...S_{H,W}

出力

全てのマスが黒く塗られた状態にするためにスタンプを押す必要のある回数の最小値を出力せよ．

入力例 1

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

出力例 1

3

例えば，下図の通りに押すと 3 回で全てのマスを黒く塗ることができる．

b50ca03a62fb58d6362e2ea94e6d1e7d.png

入力例 2

2 6
######
######

出力例 2

0