algo-aha

边角矩形的数量

• https://leetcode.com/problems/number-of-corner-rectangles/

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].

Example 2:

Input: grid = 
[[1, 1, 1],
 [1, 1, 1],
 [1, 1, 1]]
Output: 9
Explanation: There are four 2x2 rectangles, four 2x3 and 3x2 rectangles, and one 3x3 rectangle.

Example 3:

Input: grid = 
[[1, 1, 1, 1]]
Output: 0
Explanation: Rectangles must have four distinct corners.

Note:

1. The number of rows and columns ofgrid will each be in the range [1, 200].
2. Each grid[i][j] will be either 0 or 1.
3. The number of 1s in the grid will be at most 6000.

int countCornerRectangles(vector<vector<int>>& grid) {
    if (grid.empty()) return 0;
    const int R = grid.size(), C = grid[0].size();
    int ans = 0;
    // 遍历两个行
    for (int r1 = 0; r1 < R; r1++) {
        for (int r2 = r1 + 1; r2 < R; r2++) {
            int cnt = 0; // “某列两端同为1”的列数
            for (int c = 0; c < C; c++) {
                if (grid[r1][c] && grid[r2][c]) cnt++;
            }
            ans += cnt * (cnt - 1) / 2;
        }
    }
    return ans;
}