cho.sh

Rose Garden Witch

아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제

薔薇園の魔女 GERTRUD は幅 W メートル，高さ H メートルの長方形の庭でバラを育てている．庭は一辺 1 メートルの正方形で区切られており，W×H のブロックに分けられている．各ブロックはバラが育てられているか育てられていないかのどちらかである．

ただ驚くべきことに，この庭で育てられているバラはブロックを越えて絡み合い 1 つの生命体となっている．この生命体は辺を共有しているブロック間を越えて絡み合うことができ，どこかある 1 点を共有していれば同じ生命体となる．

巴マミは庭の左下の角から直線に必殺技「ティロ・フィナーレ」で巨大な銃を撃ち，その弾丸が通る直線上でその生命体を分割した時，生命体が出来る限り多くの分割数に分断されるようにすることによりダメージを与えたい．ティロ・フィナーレは最大でこの生物を何分割できるか求めよ．

입력

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

H W
f11f12…f1W
f21f22…f2W
…
fH1fH2…fHW

H は庭の高さ，W は庭の幅を表す．

fij は庭の各ブロックを表す文字であり，上から i 行目，左から j 列目のブロックの状態を表す．ブロックにバラが育てられている場合は fij は '#' となり，そうでない場合は '.' となる．

출력

生命体を直線で分割する時に，最大でいくつの部分に分割できるかを1行で出力せよ．

제한

  • 1≤H≤600
  • 1≤W≤600
  • fijは '#', '.'のいずれかである．
  • 少なくとも 1 つはfij=``'#' となるマス fij が存在する．
  • 2 つのブロックが辺を共有するとき，それらは隣接していると呼ぶことにする．任意の 2 つの異なる '#' のブロック fA,fB に対して，fA から隣接している '#' のブロックを辿っていって fB に着くことができる．(すなわち，薔薇のブロックは連結である．)
  • 入力中で 1 行目の行，H 行目の行，1 列目の列，または W 列目の列にあるブロックを盤面の端のブロックと呼ぶことにする．任意の '.' のブロック fC に対して，fC から隣接している '.' のブロックを辿っていって，ある '.' の盤面の端のブロックに着くことができる．(すなわち，入力に"空洞"のブロックは存在しない．)