No.421 しろくろチョコレート

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 315 MB / 通常問題
タグ : / 解いたユーザー数 61
作問者 : koyumeishikoyumeishi / テスター : 37zigen37zigen

7 ProblemId : 277 / 出題時の順位表

問題文

雪製菓が製造・販売するチョコレート菓子「しろくろチョコレート」は皆に大人気のお菓子です。 しろくろチョコレートは$N$×$M$個のブロックからなる板チョコですが、普通の板チョコとは一味違います。 ブロック毎に黒いビターチョコと白いホワイトチョコが交互に並んでいる、 まるでチェスボードのような、見た目の美しいチョコレート菓子なのです。

千代子ちゃんはこのチョコレートが大の好物で、下記のいずれかの食べ方をすることで幸福度を得ることができます。

  • 方法1

    板チョコの任意の位置からブロックを$1×1$の大きさに切り出し、これを食べる。
    このとき得られる幸福度は $1$。

  • 方法2

    板チョコの任意の位置からホワイトチョコのブロックとビターチョコのブロックを、 それぞれ$1×1$の大きさに切り出し、これらを同時に食べる。
    このとき得られる幸福度は $10$。

  • 方法3

    板チョコの任意の位置からホワイトチョコとビターチョコのブロックが連続する $2×1$(または$1×2$)の大きさのブロックを切り出し 、これを食べる。
    このとき得られる幸福度は $100$。

千代子ちゃんは任意の位置からブロックを切り出すことが出来るので、端の方から順に切り出す必要はありません。
しかし風味が損なわれるので、一度切ってしまったものを溶かして繋げ直すことは出来ません。
また、これら以外の方法でチョコレートを食べても幸福度は得られません。


千代子ちゃんは自分へのご褒美にしろくろチョコレートを買ってきました。 千代子ちゃんはこれを丸々一人で食べる予定だったのですが、 弟の玲斗くんが一部をつまみ食いしてしまったようです。
玲斗君がつまみ食いした後のチョコレートの状態が与えられるので、 残ったチョコレートから千代子ちゃんが得ることのできる最大の幸福度を答えてください。

入力

1行目に購入時のチョコレートの縦方向のブロック数$N$、横方向のブロック数$M$が与えられます。
以降N行に、$i$段目のチョコレートの状態が、長さ$M$の文字列$S_i$として与えられます。
$S_{i,j}$ が 'w' のとき、ブロック[$i,j$]はホワイトチョコです。
$S_{i,j}$ が 'b' のとき、ブロック[$i,j$]はビターチョコです。
$S_{i,j}$ が '.' のとき、ブロック[$i,j$]のチョコレートは既に玲斗くんが食べてしまいました。

$N$ $M$
$S_1$
$S_2$
$\vdots$
$S_N$

入力は以下の制約を満たします。
$N$、$M$は整数
$1 \leq N,M \leq 50$
$|S_i| = M$
$i+j$ が偶数のとき、$S_{i,j} = $ 'w' または '.'
$i+j$ が奇数のとき、$S_{i,j} = $'b' または '.'

出力

千代子ちゃんが得ることのできる最大の幸福度を一行に出力してください。 最後に改行してください。

サンプル

サンプル1
入力
2 3
wbw
bw.
出力
201

$2×1$のブロックを2つ、$1×1$のブロックを1つ切り出して食べると幸福度201を得られます。

サンプル2
入力
3 4
wb..
b..w
..wb
出力
210

チョコレートが繋がっていない場合もあります。
例えば以下のように切り出すと幸福度210を得られます。

サンプル3
入力
4 4
wbwb
b...
wbwb
...w
出力
500

提出ページヘ