〜魔女からこの世界を守るためキュゥべえと共に戦う 5 人の魔法少女達の物語〜
問題 A
問題文
薔薇園の魔女 GERTRUD は幅 W メートル，高さ H メートルの長方形の庭でバラを育てている．庭は一辺 1 メートルの正方形で区切られており，W\times H のブロックに分けられている．各ブロックはバラが育てられているか育てられていないかのどちらかである．ただ驚くべきことに，この庭で育てられているバラはブロックを越えて絡み合い 1 つの生命体となっている．この生命体は辺を共有しているブロック間を越えて絡み合うことができ，どこかある 1 点を共有していれば同じ生命体となる．
巴マミは庭の左下の角から直線に必殺技「ティロ・フィナーレ」で巨大な銃を撃ち，その弾丸が通る直線上でその生命体を分割した時，生命体が出来る限り多くの分割数に分断されるようにすることによりダメージを与えたい．ティロ・フィナーレは最大でこの生物を何分割できるか求めよ．
入力形式
入力は以下の形式で与えられる．
H\ W\\
f_{11} f_{12} ... f_{1W}\\
f_{21} f_{22} ... f_{2W}\\
...\\
f_{H1} f_{H2} ... f_{HW}\\
H は庭の高さ，W は庭の幅を表す．
f_{ij} は庭の各ブロックを表す文字であり，上から i 行目，左から j 列目のブロックの状態を表す．ブロックにバラが育てられている場合は f_{ij} は '#' となり，そうでない場合は '.' となる．
出力形式
生命体を直線で分割する時に，最大でいくつの部分に分割できるかを1行で出力せよ．制約
- 1 ≤ H ≤ 600
- 1 ≤ W ≤ 600
- f_{ij}は
'#','.'のいずれかである． - 少なくとも 1 つはf_{ij} =
'#'となるマス f_{ij} が存在する． - 2 つのブロックが辺を共有するとき，それらは隣接していると呼ぶことにする．任意の 2 つの異なる
'#'のブロック f_A, f_B に対して，f_A から隣接している'#'のブロックを辿っていって f_B に着くことができる．(すなわち，薔薇のブロックは連結である．) - 入力中で 1 行目の行，H 行目の行，1 列目の列，または W 列目の列にあるブロックを盤面の端のブロックと呼ぶことにする．任意の
'.'のブロック f_C に対して，f_C から隣接している'.'のブロックを辿っていって，ある'.'の盤面の端のブロックに着くことができる．(すなわち，入力に"空洞"のブロックは存在しない．)
入出力例
入力例 1
3 5 ##..# #..## ####.
出力例1
4このとき以下のように 4 つの部分に分割することができる．
入力例 2
3 3 #.# ### #.#
出力例 2
3
入力例 3
10 9 ......... ......... ####..... #..#.##.. #..#..#.. #..##.### #..##...# ##..##.## ###.#..#. ###.####.
出力例 3
6
入力例 4
10 11 ########### #.#.#.#.#.# #.#.#.#.#.# #.#.#.#.#.# #.#.#.#.#.# #.#.#.#.#.# #.#.#.#.#.# #.#.#.#.#.# #.#.#.#.#.# #.#.#.#.#.#
出力例 4
7
入力例 5
25 38 ...........#...............#.......... ...........###..........####.......... ...........#####.......####........... ............###############........... ............###############........... ............##############............ .............#############............ ............###############........... ...........#################.......... .......#...#################...#...... .......##.##################..##...... ........####################.##....... ..........####################........ .........#####..########..#####....... .......######....#####....######...... ......########...#####..########.#.... ....#######..#...#####..#..########... ..#########.....#######......#######.. ...#######......#######........###.... ..####.........#########........###... ...............#########.............. ..............##########.............. ..............##########.............. ...............########............... ...............########...............
出力例 5
8
Problem Setter: Flat35