L 750. Number Of Corner Rectangles -----M !!!!!!

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.

 

A:

首先考虑的是遍历所有的top left, and bottom right corner. 对其每个pair， 看是否构成了 corner rectangle. （ LTE)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

class Solution { public: int countCornerRectangles(vector<vector<int>>& grid) { int m = grid.size(); if(m==0){ return 0; } int n = grid[0].size(); vector<pair<int,int>> V; for(int i=0;i<m ; i++){ for(int j =0; j<n; j++){ if(grid[i][j]) V.push_back(make_pair(i,j)); } } int res = 0; for(int i = 0;i<V.size();i++){ for(int j = i+1; j<V.size();j++){ if(V[i].first == V[j].first || V[i].second == V[j].second) continue; // make sure V[i] is on the left side of V[j] ( as it is guaranteed to be on the top of V[j]) if(V[i].second > V[j].second) continue; if(grid[V[i].first][V[j].second] && grid[V[j].first][V[i].second]){ ++res; } } } return res; } };

Mistakes：

没有检查 ，top left 的位置要在bottom right的左边。

***********************上面的超时了，  思路2 **********************

想象每一行，我们所有的 1, 两两可以组成一条线段。map成一个数字。 那么以后，如果想和他组成corner rectangle, 必须下面的row， 也有column 值组成这样的线段。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

class Solution { public: int countCornerRectangles(vector<vector<int>>& grid) { int m = grid.size(); if(m==0){ return 0; } int n = grid[0].size(); unordered_map<int,int> M; for(int i =0;i<m;i++){ // for each row, mapping possible line vector<int> V; for(int j=0;j<n; j++){ if(grid[i][j]){ V.push_back(j); } } // for each pair of 1 in current line for(int k = 0; k<V.size(); k++){ for(int t = k+1; t<V.size(); t++){ M[V[k] * 201 + V[t]]++; } } } int res = 0; for(auto& it : M){ res += it.second * (it.second - 1) / 2; } return res; } };