塔防建造

题目描述

育华学校编程社团设计了一款校园主题游戏，游戏地图由 $n \times m$ 的矩形网格构成，每个格子对应校园里的一处区域，可能是空地（用 0 表示 ），也可能有“模拟怪物”（用 1 表示 ）。

玩家需要在空地上建造防卫塔，防卫塔只能朝上下左右四个方向中的一个发射无限距离的激光。一旦选定攻击方向，就无法修改。

现在，社团成员要完成新手任务：选择一块空地建造防卫塔，且这座塔至少能击杀一个“模拟怪物”。需要计算有多少种不同的建造方案（同一个空地选不同攻击方向视为不同方案 ）。

输入格式

第一行输入两个空格隔开的整数 $n$ 和 $m$ ，表示网格的行数和列数。
接下来 $n$ 行，每行输入 $m$ 个整数（0 或 1 ），描述网格中每个格子的情况（0 是空地，1 是“模拟怪物” ）。

输出格式

输出一个整数，表示符合要求的建造方案总数。

样例

样例输入 1

2 4  
0 1 0 0  
1 0 1 0  

样例输出 1

9  

样例解释 1

• $(1,1)$ 位置（行、列从 1 开始计数 ）：
  防卫塔向下、向右攻击可击杀怪物，共 2 种方案。
• $(1,3)$ 位置：
  防卫塔向左、向下攻击可击杀怪物，共 2 种方案。
• $(1,4)$ 位置：
  防卫塔向左攻击可击杀怪物，共 1 种方案。
• $(2,2)$ 位置：
  防卫塔向左、向右、向上攻击可击杀怪物，共 3 种方案。
• $(2,4)$ 位置：
  防卫塔向左攻击可击杀怪物，共 1 种方案。
  总共有 $2 + 2 + 1 + 3 + 1 = 9$ 种方案。

样例输入 2

4 4  
0 0 1 0  
1 0 1 1  
1 0 0 0  
0 0 0 0  

样例输出 2

15  

数据规模与约定

• 30% 的数据：$n = 1$，$1 \leq m \leq 100$
• 90% 的数据：$1 \leq n, m \leq 100$
• 100% 的数据：$1 \leq n, m \leq 1000$