C.涂鸦连线（Doodle）

题目描述

小明在一张 (R\times C) 的方格纸上涂黑了若干格。画作中存在一条由连续黑格组成的路径，从左上角 ((0,0)) 连接到右下角 ((R-1,C-1))，称为对角路径。

两个方格共享一条边时才视为相邻。对角路径满足：

• 起点和终点各恰好与一个黑格相邻；
• 路径中间的每个黑格都恰好与两个黑格相邻；
• 路径中不会出现 (2\times2) 的区域全部为黑格。

方格纸上还可能有不属于这条路径的黑格。请计算对角路径包含的黑格数量。

方格纸中的对角路径包含 (17) 个黑格】

输入格式

第一行包含两个整数 (R,C)（(1\le R,C\le20)），表示方格纸的行数和列数。

接下来 (R) 行，每行包含 (C) 个整数，相邻整数以空格分隔：

• 0：该格没有涂黑；
• 1：该格已涂黑。

输出格式

输出一个整数，表示从左上角到右下角的对角路径包含的黑格数量。

样例 1

输入

6 6
1 0 0 0 0 0
1 1 1 1 0 0
0 0 0 1 0 0
0 0 0 1 0 0
0 0 0 1 1 0
0 0 0 0 1 1

输出

11

样例 2

输入

8 8
1 1 1 0 1 0 0 0
0 0 1 0 1 1 1 1
0 0 1 1 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 1 0 0 0 0
1 1 0 1 0 1 1 1
0 1 0 1 1 1 0 1
0 1 0 0 0 0 0 1

输出

17

评分说明

每组包含多笔测试数据，只有答对该组的全部数据才能获得对应分数。