You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题面背景

激光防御塔

题目描述

你最近在玩一个游戏，这个游戏地图由一个 $n \times m$ 的矩形地图构成，每个坐标都对应一个格子。

每个格子中可能存在怪物，也可能是空地，玩家需要在地图上建造防御塔来击杀怪物。

但是在这个游戏中，一个防御塔只能朝 上下左右 四个方向其中一个发射激光（攻击距离无限），当防御塔选择攻击方向以后就不允许修改了。

现在你的新手任务是选择一个空地建造一座防御塔，要求这座防御塔能击杀至少一个怪物。

我们想知道有多少种不同的方案来建造这座防御塔？

$P.S.$ 同一个格子不同方向的防御塔也被认为是不同的方案。

输入格式

第一行输入两个空格隔开的整数 $n, m$。

接下来 $n$ 行，每行输入 $m$ 个整数，每个整数是 $0$ 或者 $1$。

$0$ 表示这个格子是空地，$1$ 表示这个格子上有一个怪物。

输出格式

一行一个整数，表示有多少个格子没被影响。

样例 #1

样例输入 #1

2 4
0 1 0 0
1 0 1 0

样例输出 #1

9

样例1解释

• 在$(1, 1)$位置，防御塔向下和向右攻击都可以击杀怪物，有$2$种方案。
• 在$(1, 3)$位置，防御塔向左和向下攻击都可以击杀怪物，有$2$种方案。
• 在$(1, 4)$位置，防御塔向左攻击可以击杀怪物，有$1$种方案。
• 在$(2, 2)$位置，防御塔向左、向右和向上攻击可以击杀怪物，有$3$种方案。
• 在$(2, 4)$位置，防御塔向左攻击可以击杀怪物，有$1$种方案。

所以总共有$9$种方案。

数据范围

• 对于 $100\%$ 的数据，$1\le n, m \le 1000，1\le t \le 10^4, 1 \le x_i \le n, 1 \le y_i \le m$