C - チョコレート
Editorial
/
Time Limit: 2 sec / Memory Limit: 128 MB
目の前に M \times N 個のピースでできた板チョコがある. ピースには甘いピースと辛いピースの2種類があり,できるだけ多くの甘いピースを食べたい.
しかし,板チョコの食べ方にはルールがあり,以下のルールを守らなければならない.
- あるピースを食べるためには,そのピースの真上に隣接するピースが存在せず,加えてそのピースの少なくとも左右どちらかにはピースが存在しない必要がある.
例えば,図のような形のチョコレートでは,赤く色付けされたピースを次に食べることができる.
また奇妙なことに,あるピースを食べるとそのピースの上下左右に隣接していてかつまだ食べられていないピースの味が変化する. (甘いピースは辛く,辛いピースは甘くなってしまう)
上手くチョコレートを食べると最大でいくつの甘いピースを食べることができるだろうか?
入力形式
入力は以下の形式で与えられる.
M N a_{11} … a_{1N} a_{21} … a_{2N} ︙ a_{M1} … a_{MN}
a_{ij} = 0 のとき上からi番目,左からj番目のピースが辛く, a_{ij} = 1 のとき上からi番目,左からj番目のピースが甘いことを表わしている.
出力形式
食べることのできる甘いピースの個数の最大値を一行に出力せよ.
制約
- 1 \leq N,M \leq 100
- 0 \leq a_{ij} \leq 1
- 入力値はすべて整数である.
入出力例
入力例1
2 3 1 1 1 1 1 1
出力例1
5
入力例2
4 2 1 0 0 1 0 1 0 1
出力例2
8