# 750. Number Of Corner Rectangles 角矩形的数量

@TOC

## # 题目描述

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 of grid 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.

## # 解题方法

### # 遍历

C++代码如下：

``````class Solution {
public:
int countCornerRectangles(vector<vector<int>>& grid) {
if (!grid.size() || !grid[0].size()) return 0;
const int M = grid.size();
const int N = grid[0].size();
int res = 0;
for (int row1 = 0; row1 < M; ++row1) {
for (int row2 = row1 + 1; row2 < M; ++row2) {
int count = 0;
for (int col = 0; col < N; ++col) {
if (grid[row1][col] == 1 && grid[row2][col] == 1) {
count ++;
}
}
res += count * (count - 1) / 2;
}
}
return res;
}
};
``````

## # 日期

2019 年 9 月 24 日 —— 梦见回到了小学，小学已经芳草萋萋破败不堪