#740. 徐老师的新手任务
徐老师的新手任务
说明
徐老师最近在玩一个游戏,这个游戏地图由一个 $n * m$ 的矩形地图构成,每个坐标都对应一个格子。
每个格子中可能存在怪物,也可能是空地,玩家需要在地图上建造防御塔来击杀怪物。
但是在这个游戏中,一个防御塔只能朝 `上下左右` 四个方向其中一个发射激光(攻击距离无限),当防御塔选择攻击方向以后就不允许修改了
现在徐老师的新手任务是选择一个空地建造一座防御塔,要求这座防御塔能击杀至少一个怪物
徐老师希望能够完美完成新手任务,所以他想知道有多少种不同的方案来建造这座防御塔?
P.S. 同一个格子不同方向的防御塔也被认为是不同的方案
输入格式
第一行输入两个空格隔开的整数 $n,m$。
接下来 $n$ 行,每行输入 $m$ 个整数,每个整数是 $0$ 或者 $1$。
$0$ 表示这个格子是空地,$1$ 表示这个格子上有一个怪物。
对于 $30\%$ 的数据:$n = 1, 1 \le m \le 100$。
对于 $60\%$ 的数据:$1 \le n, m \le 100$。
对于 $100\%$ 的数据:$1 \le n, m \le 1000$。
输出格式
输出一个整数,表示合适的摆放位置总数。
样例
2 4
0 1 0 0
1 0 1 0
9