解题思路

思路与算法

对每个格子，想知道四个方向上是否存在 1。 可以分别做四次线性扫（行/列的前后缀）来预处理出四个布尔值：

• L[i][j]：在第 i 行，j 左侧是否出现过 1（从左往右扫描）
• R[i][j]：在第 i 行，j 右侧是否存在 1（从右往左扫描）
• U[i][j]：在第 j 列，i 上方是否出现过 1（从上往下扫描）

题目内容

在未来的霓虹都市中，每到夜晚，城市中的智能聚光灯会自动扫描四周，寻找行人并点亮方向，为城市节省能源。每个聚光灯 $(0)$ 会朝上、下、左、右四个方向无限延伸地扫描，若某方向上有至少一个行人，则该聚光灯获得 $1$ 分。

作为城市的能源工程师，你需要计算：所有聚光灯在四个方向上总共能获得多少分?

备注说明

霓虹都市的布局是一个矩阵，矩阵中的每个单元格代表城市的一块街区，街区被标记为 $0$ 或者 $1$ ：

• $1$ 表示街区中有行人。

• $0$ 表示安装了聚光灯。

聚光灯的扫描逻辑：每个聚光灯会朝四个方向无限延伸地扫描。若某方向上有至少一个行人，则该方向得 $1$ 分。

你的任务目标：统计所有聚光灯的总得分。

(注意:本题的输入数据较大，使用 $python$ 的同学请用 $pypy$ 提交，否则可能会超时!)

输入描述

输入为矩阵，第一行两个正整数 $N$ 和 $M(1<=N,M<=10^3)$ ，分别表示矩阵的行数和列数。

接下来 $N$ 行，每行 $M$ 个正整数 $a[i][j]$ ，表示表示街区的布局：

$0$ 表示聚光灯。

$1$ 表示行人。

输出描述

一个正整数，表示所有聚光灯的总得分。

样例1

输入

2 4
0 1 0 0

输出

9

说明

$(1，1)$ 的灯可以获得 $2$ 分(向右、向下)

$(1，3)$ 的灯可以获得 $2$ 分(向左、向下)

$(1，4)$ 的灯可以获得 $1$ 分(向左)

$(2，2)$ 的灯可以获得 $3$ 分(向左，向右，向上)

$(2，4)$ 的灯可以获得 $1$ 分(向左)

总和 $9$ 分。