0164 - ACM洋菓子店

先月自分の店をオープンしたお菓子職人のアンバー・C・マエスは，店の宣伝のために ICPC (International Chocolate Patissier Competition)に出品することにした． そのために，板チョコレートの試作を繰り返していたアンバーは， ついに本当においしいレシピを発見した．しかし，そのレシピではチョコレートをきれいな長方形に整形するために高度な技術が必要だった．つい今しがたも図G-1に示すような， おかしな形の板チョコレートを作ってしまったところだ．

図 G-1: おかしな形の板チョコレート

板チョコレートはたくさんの小長方形のチョコレートでできている．隣接する小長方形の間には溝が掘られており，割りやすくなっている． アンバーは，おかしな形の板チョコレートをいくつかの長方形の断片に切り分けて店で売ろうと考えた．彼女は次のように板チョコレートを切ることにした．

• 板チョコレートは溝に沿って切る．
• 断片が全て長方形になるように切り分ける．
• できるだけ少ない数の断片に切り分ける．

このルールに従えば，図G-1は例えば図G-2のように切り分けられる． 図G-3には長方形でない断片が含まれており，図G-4は図G-2よりも多くの断片に切り分けているため，ルールに従っていない．

図 G-2: ルールに従って切り分けた例

図 G-3: 長方形でない断片を含むような切り分け方の例

図 G-4: 図G-2よりも多くの断片に切り分ける例

あなたの仕事は，このルールに従って板チョコレートを切り分けた時，いくつの断片に分かれるかを求めるプログラムを作ることである．

入力は，複数のデータセットからなり，入力の終わりはスペースで区切られたゼロ2つからなる行である．各データセットは，次の形式をしている．

h w
r_{(1, 1)} ... r_{(1, w)}
r_{(2, 1)} ... r_{(2, w)}
...
r_{(h, 1)} ... r_{(h, w)}

h と w は，板チョコレートの直交する2方向の長さを小長方形チョコレートの数で表した整数であり，2 ≤ h ≤ 100, 2 ≤ w ≤ 100 と仮定してよい．続く h 行はそれぞれ， w 個の文字で構成されており， 文字 r_{(i, j)} は，場所 (i, j) の小長方形チョコレートの有無を表す．文字の意味は，次の通り．

• ".": 小長方形チョコレートなし
• "#": 小長方形チョコレートあり

連結していない板チョコレート(図G-5)や穴のある形の板チョコレート(図G-6や図G-7)を表すようなデータセットが無いことを仮定してよい．また，各データセットには少なくとも1つの"#"の文字が含まれていることを仮定してよい．

図 G-5: 連結していない板チョコレート

図 G-6: 穴のある形の板チョコレート

図 G-7: 穴のある形の板チョコレートのもう1つの例

入力データセットごとに，ルールに従って切り分けた時の断片の数を表す整数のみからなる行を出力せよ．

3 5
###.#
#####
###..
4 5
.#.##
.####
####.
##.#.
8 8
.#.#.#.#
########
.######.
########
.######.
########
.######.
########
8 8
.#.#.#.#
########
.##.#.#.
##....##
.##.###.
##...###
.##.###.
###.#.##
4 4
####
####
####
####
0 0

3
5
11
19
1