leetcode：1139. The largest square bounded by 1

Title source

• leetcode：1139. The biggest one is 1 For the square of the boundary

Title Description

class Solution {
    
public:
    int largest1BorderedSquare(vector<vector<int>>& grid) {
    

    }
};

for instance ： It can be seen with the naked eye that the side length of an array that meets the conditions is 33 , It is also the largest side length .

vector<vector<int>> grid ={
     {
    0, 1, 0, 1, 1},
							{
    1, 1, 1, 1, 1},
							{
    1, 1, 0, 1, 1},
							{
    1, 1, 1, 1, 0},
							{
    0, 1, 1, 1, 1},
							{
    1, 1, 1, 0, 1},
							{
    0, 1, 1, 1, 1},
							{
    1, 1, 1, 0, 1}
};


std::vector<std::vector<int>> grid = {
    
            {
    1, 1, 1},
            {
    1, 0, 1},
            {
    1, 1, 1}
    };

title

Dynamic programming

class Solution {
    
public:
    //  Using the idea of dynamic planning , Create a three-dimensional array to store the left and top continuous 1 The number of 
    int largest1BorderedSquare(vector<vector<int>>& grid) {
    
        if(grid.empty()){
    
            return 0;
        }
        int length = grid.size(); // Length of matrix 
        int width = grid[0].size(); // The width of the matrix 

        // use dp[i][j][0] To represent the i Xing di j Column   On the left   Successive 1 The number of 
        // use dp[i][j][1] To represent the i Xing di j Column   above   Successive 1 The number of 
        std::vector<std::vector<std::vector<int>>> dp(
                   length + 1, std::vector<std::vector<int>>(
                    width + 1, std::vector<int>(
                    2, 0
                                )
                        )
                );

        int maxLen = 0;
        for (int i = 1; i <= length; ++i) {
    
            for (int j = 1; j <= width; ++j) {
    
                if(grid[i - 1][j - 1] == 1){
      // Because the code above  i  and  j  from 1 Start , To m,n end , It can be understood as adding a layer on the left and top of the rectangle 0, So actually dp[i][j][0] It's actually grid[i-1][j-1] Continuous on the left 1 The number of （ Include yourself ）, This is actually done to facilitate initialization , Avoid writing too much if-else, Is a very common skill 
                    dp[i][j][0] += dp[i][j - 1][0] + 1;
                    dp[i][j][1] += dp[i - 1][j][1] + 1;
                    
                    // Try to i Xing di j Column ( Current point ) Form a square for the lower right corner 
                    int len = std::min(dp[i][j][0], dp[i][j][1]); // Maximum possible length 
                    while (len > 0){
    
                        // Judge whether there is continuity on the left side of the upper right corner of this possible square len individual 1 &&  Whether there is continuity above the lower left corner len individual 1
                        if(dp[i - len + 1][j][0] >= len && dp[i][j - len + 1][1] >= len){
    
                            break;
                        }
                        len--;
                    }
                    maxLen = std::max(maxLen, len);
                }
            }
        }
        return maxLen * maxLen;
    }
};