Leetcode題解 Python & C#：五月挑戰DAY21 Count Square Submatrices with All Ones

給一個由 0 1 組成的矩陣，回傳有多少個正方形全部都是 1 。

這題蠻容易的，就算用暴力法 + dp ，也不會被判超時。

如果本身是 1 ，自己能形成一個正方形，然後往四角延伸去看是否能構成更大的正方形。

用 y x 由上至下，由左至右，所以選右下作基準點。那麼能構成更大的正方形，是其左上、左、上都是同一個數字。

如構成 2 * 2：

[[1,1],

[1,2]] 

位置[1][1]的點，其左上、左、上都是 1 ，所以可以構成 2(1+1)。

3 * 3：

[[1,1,1],

[1,2,2],

[1,2,3]]

位置[2][2]的點，其左上、左、上都是 2 ，所以可以構成 3(2+1)。3 表示該位置有(1*1、2*2、3*3)的正方形。

位置[2][1]的點，其左上2、左1、上1，所以可以構成 2(1+1)。

也就是說，是左上、左、上中取最小值+1。前提也要該位置本來是 1 才可以這樣處理。

Python

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:             
        result = 0
        cols = len(matrix[0])
        for y in range(len(matrix)):
            for x in range(cols):
                if matrix[y][x] == 1:
                    if y - 1 >= 0 and x - 1 >= 0:
                        matrix[y][x] = min(matrix[y-1][x-1], matrix[y][x-1], matrix[y-1][x]) + 1
                    result += matrix[y][x]                        
        return result
                        

C#

public class Solution {
    public int CountSquares(int[][] matrix) {
        int result = 0;
        for(int y = 0; y < matrix.Length; y++)
        {
            for(int x = 0; x < matrix[0].Length; x++)
            {
                if(matrix[y][x] == 1)
                {
                    if(y >= 1 && x >= 1)
                    {                        
                        matrix[y][x] = 1 + Math.Min(matrix[y-1][x], Math.Min(matrix[y-1][x-1], matrix[y][x-1]));
                    }
                    result += matrix[y][x];
                }                
            }
        }
        return result;
    }
}