← 返回 waymo 的题目列表Count Fertile Pyramids in a Land
类型：online_judge
Problem: Count Fertile Pyramids in a Land
Given an m x n binary matrix grid:
grid[i][j] = 1 means the cell is fertile land;
grid[i][j] = 0 means the cell is not fertile land.
A pyramidal plot consists of several levels and must satisfy:
Its height is at least 2;
Every cell in the plot is fertile;
An upright pyramid has its apex at the top. At depth k from the apex, the level width is 2k + 1;
An inverted pyramid is the vertical flip of an upright pyramid.
Return the total number of upright and inverted fertile pyramids in the grid.
Input Format
m n
grid[0][0] grid[0][1] ... grid[0][n-1]
...
grid[m-1][0] grid[m-1][1] ... grid[m-1][n-1]
Output Format
answer
Constraints
1 <= m, n <= 1000
grid[i][j] is either 0 or 1
Example
Input:
2 4
0 1 1 0
1 1 1 1
Output:
2
Example
Input
2 4
0 1 1 0
1 1 1 1
Output
2