Description
Given a grid of 0s and 1s, count the number of axis-aligned rectangles that can be formed using only grid cells marked with 1 as corners. Return the result as an integer.
Examples
Input:
grid = [[1,0,0,1,0],[0,0,1,0,1],[0,0,0,1,0],[1,0,1,0,1]]Output:
6Explanation:
One corner rectangle.
Input:
grid = [[1]]Output:
0Explanation:
A single cell with value 1 cannot form any corner rectangle since rectangles require at least 4 corners across at least 2 rows and 2 columns.
Input:
grid = [[1,1,0],[1,1,0],[0,0,1]]Output:
3Explanation:
There is one corner rectangle formed by the 1s at positions (0,0), (0,1), (1,0), and (1,1). These four 1s form a 2x2 rectangle in the top-left corner of the grid.
Constraints
- •
1 ≤ rows, cols ≤ 200