先月自分の店をオープンしたお菓子職人のアンバー・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つの例