G - Stamps 2 Editorial /

Time Limit: 2 sec / Memory Limit: 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} で表され，# は黒く塗られていること，. は塗られていないことを意味する．

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

このスタンプセットには 2 種類のスタンプが入っており，それぞれ下図のようなマスの集合を一度に黒く塗ることができる．

2634fdc1c331a3ef57daf72b5bc2be7f.png

すなわち，

  • 左のスタンプを 1 回押すと，整数 i_0,j_0 を選んだとき，i = i_0+5a+2b, j = j_0-2a+5b となる整数 a,b が存在するようなマス (i,j) を全て黒く塗ることができる．
  • 右のスタンプを 1 回押すと，整数 i_0,j_0 を選んだとき，i = i_0+2a+5b, j = j_0-5a+2b となる整数 a,b が存在するようなマス (i,j) を全て黒く塗ることができる．

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

制約

  • 1 \le H,W \le 300
  • 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

8 8
.####.##
########
.####.##
########
########
##.####.
########
##.####.

出力例 1

3

入力例 2

50 50
######################.#.##.######################
##############.########################.###..#####
####.###############..############################
###################.###########.####.#############
########.#.#####################.##########..#####
###.###.#####.######.######.##############.###.##.
.########.###.###############..#######.###.####.#.
.#.###############.######.#####.###############..#
####.########################.###.##.#############
################.#####.#.#########.#.#############
..#########.############.#########.#####.######.##
######.###############.#####.###########..########
###.##########.#.##########..################.####
################.###########################.##.##
#####.############.....#####.####..###############
#.#####################.####.#.######..##########.
#########.#.########.#.###.############.##.#######
########.####.####################.#######.#..####
##.#####.####.################.#######.#######.###
..#######.#.#################.###.##############..
#.######.####.#####.#.####.#####.##.#####..#######
################.#######..#####.##################
########.###..#########..###.########.###.######.#
#############################.######.###########.#
##..#############.#############..#########.####.##
############.###########.###.##############..#####
.#####..###############.#########.#.#########.####
#.########.############.#########.############.###
###.#.####################..###########.#..#######
#####.###.##############.##.##########.#####.#####
#######.##.#####.##########.###############.######
.#########.################.#####.#########.######
##.############.###..###########.###.#.##.######.#
##############..#######.#############.######.#####
###.################.###..######.##..#########.###
#.##################.########.########..##########
.#.#########.#####################################
#######.###########.#########.#####.############..
#.####################.##..###.###.###############
###########.############.####..###################
.###########.#########.#################.#########
##############.#..##############..#########.######
###..##.##########################.###########.###
#########.##########.#.#####.####.################
#.######.##.################.#.######.#.#####.####
#########.######.###.#.###.######.###.#.#####.####
###############.##################.#######.#..####
#.######.#######..#############..#########.##.####
#########.###########.####.###########.#########.#
######.#.###########.#####.###.##.#######..######.

出力例 2

15

入力例 3

1 1
#

出力例 3

0