# LeetCode: 750. 角矩形的数量¶

## 1、题目描述¶

输入：grid =
[[1, 0, 0, 1, 0],
[0, 0, 1, 0, 1],
[0, 0, 0, 1, 0],
[1, 0, 1, 0, 1]]



输入：grid =
[[1, 1, 1],
[1, 1, 1],
[1, 1, 1]]



输入：grid =
[[1, 1, 1, 1]]



• 网格 grid 中行和列的数目范围为 [1, 200]
• Each grid[i][j] will be either 0 or 1.
• 网格中 1 的个数不会超过 6000

## 2、解题思路¶

• 找出不同列的组合，两个点都为以的行的个数，然后找出两两组合的数量
例如
[[1, 0, 0, 1, 0],
[0, 0, 1, 0, 1],
[0, 0, 0, 1, 0],
[1, 0, 1, 0, 1]]

找出 第0列和第一列都为1的行数  ： 0

import math
from itertools import combinations

class Solution:
def countCornerRectangles(self, grid: List[List[int]]) -> int:
if len(grid) < 2 or len(grid[0]) < 2:
return 0
row, col = len(grid), len(grid[0])
ans = 0

def comb(n, m):
return math.factorial(n) // (math.factorial(n - m) * math.factorial(m))

for x, y in combinations(range(col), 2):
cur_count = 0
for r in range(row):
if grid[r][x] == 1 and grid[r][y] == 1:
cur_count += 1
if cur_count >= 2:
ans += comb(cur_count, 2)
return ans

• 借助集合，找出组合数量
from collections import defaultdict

class Solution:
def countCornerRectangles(self, grid: List[List[int]]) -> int:
if len(grid) < 2 or len(grid[0]) < 2:
return 0
row, col = len(grid), len(grid[0])
ans = 0

cols = defaultdict(set)
for i in range(row):
for j in range(col):
if grid[i][j] == 1: