题目
Given a grid where each entry is only 0 or 1, find the number of corner rectangles.
A corner rectangle is 4 distinct 1s on the grid that form an axis-aligned rectangle. Note that only the corners need to have the value 1. Also, all four 1s used must be distinct.
Example 1:
Input: grid =
[[1, 0, 0, 1, 0],
[0, 0, 1, 0, 1],
[0, 0, 0, 1, 0],
[1, 0, 1, 0, 1]]
Output: 1
Explanation: There is only one corner rectangle, with corners grid[1][2], grid[1][4], grid[3][2], grid[3][4].
Note:
The number of rows and columns of grid will each be in the range [1, 200].
Each grid[i][j] will be either 0 or 1.
The number of 1s in the grid will be at most 6000.
答案
class Solution {
public int countCornerRectangles(int[][] grid) {
// Grid[i][j] is current point, grid[k][p] is diagonal point
/*
(i,j) (i,p)
(k,j) (k,p)
*/
int count = 0;
for(int i = 0; i < grid.length; i++) {
for(int j = 0; j < grid[0].length; j++) {
for(int k = i + 1; k < grid.length && grid[i][j] == 1; k++) {
for(int p = j + 1; p < grid[0].length && grid[k][j] == 1; p++) {
count += grid[k][p] * grid[i][p];
}
}
}
}
return count;
}
}