对每个格子,想知道四个方向上是否存在 1。
可以分别做四次线性扫(行/列的前后缀)来预处理出四个布尔值:
L[i][j]:在第 i 行,j 左侧是否出现过 1(从左往右扫描)R[i][j]:在第 i 行,j 右侧是否存在 1(从右往左扫描)在未来的霓虹都市中,每到夜晚,城市中的智能聚光灯会自动扫描四周,寻找行人并点亮方向,为城市节省能源。每个聚光灯 (0) 会朝上、下、左、右四个方向无限延伸地扫描,若某方向上有至少一个行人,则该聚光灯获得 1 分。
作为城市的能源工程师,你需要计算:所有聚光灯在四个方向上总共能获得多少分?
备注说明