[leetcode 221] Maximal Square

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

Example:

Input:

1 0 1 0

0 1 0 1

1 1 1 1

1 1 1 1

0 0 1 0

Output: 4

 

풀이

: 최대 길이를 return 하게 만들자. dp[i][j]는 dp[i][j]를 포함하여 만들 수 있는 최대 정사각형 길이

dp[i-1][j-1]을 중심으로

1 1 자신을 제외한 주변 숫자들이 0이상의 수로 동일하면 +1

 1 2

 

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        
        int row = matrix.size();
    
        if(row==0){
            return 0;
        }
        int col = matrix[0].size();
        
        
        int dp[row +1][col+1];
        
        memset(dp, 0, sizeof(dp));
        
        int result=0;
        
        for(int i=0; i<row; i++){
            for(int j=0; j<col; j++){
                if(i==0 || j==0){
                    dp[i][j] = matrix[i][j] == '1'? 1:0;
                     result = max(result, dp[i][j]);
                } else if(matrix[i][j] == '1'){
                    dp[i][j] = min(min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) +1;
                     result = max(result, dp[i][j]);
                }
                
            }
        }
        return result * result;
    }
};