LeetCode 750. 角矩形的数量（DP）

示例 1：
输入：grid = 
[[1, 0, 0, 1, 0],
 [0, 0, 1, 0, 1],
 [0, 0, 0, 1, 0],
 [1, 0, 1, 0, 1]]
输出：1
解释：只有一个角矩形，角的位置为 grid[1][2], grid[1][4], grid[3][2], grid[3][4]。

示例 2：
输入：grid = 
[[1, 1, 1],
 [1, 1, 1],
 [1, 1, 1]]
输出：9
解释：这里有 4 个 2x2 的矩形，4 个 2x3 和 3x2 的矩形和 1 个 3x3 的矩形。

示例 3：
输入：grid = 
[[1, 1, 1, 1]]
输出：0
解释：矩形必须有 4 个不同的角。
 
提示：
网格 grid 中行和列的数目范围为 [1, 200]。
每个网格 grid[i][j] 中的值不是 0 就是 1 。
网格中 1 的个数不会超过 6000。

class Solution {
public:
    int countCornerRectangles(vector<vector<int>>& grid) {
    	int m = grid.size(), n = grid[0].size(), r, c1, c2, count = 0;
        vector<vector<int>> dp(n, vector<int>(n, 0));
        for(r = 0; r < m; ++r)
        {
        	for(c1 = 0; c1 < n; ++c1)
        	{
        		if(grid[r][c1])
        		{
        			for(c2 = c1+1; c2 < n; ++c2)
        			{
        				if(grid[r][c2])
        				{
        					count += dp[c1][c2];
        					dp[c1][c2]++;
        				}
        			}
        		}
        	}
        }
        return count;
    }
};