← 返回题目列表

AtCoder · kupc2013_c

C. 巧克力

中文机器翻译题面 查看原题

就在你面前 有一块由 M \times N 块制成的巧克力棒。 片有两种:甜片和辣片,你想吃尽可能多的甜片。

但是,如何吃巧克力是有规则的,必须遵守以下规则。

  • 为了吃掉某个棋子,它的正上方不能有相邻的棋子,此外,该棋子的左侧或右侧至少不能有任何棋子。

例如,巧克力形状如图所示,接下来可以吃红色的那块。

[原图]

另外,奇怪的是,当你吃掉某一块时,上、下、左、右与该块相邻但尚未被吃掉的块的味道会发生变化。 (甜的变辣,辣的变甜)

巧克力吃得好,能吃多少颗甜品?

入力形式

输入按以下格式给出。

  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