leetcode Maximal Square

题目

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

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Return 4.
题目来源：https://leetcode.com/problems/maximal-square/

分析

动态规划。关注正方形右下角，dp[i][j]存储以当前顶点为正方形右下角的正方形的边长。遍历的过程中如果matrix[i][j] == ‘1’，则dp[i][j] = min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1]) + 1；如果matrix[i][j] == ‘0’，那dp[i][j]肯定是0了。

代码

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int m = matrix.size();
        if(m == 0)
            return 0;
        int n = matrix[0].size();
        vector<vector<int> > dp(m, vector<int>(n, 0));
        int ans = 0;
        for(int i = 0; i < m; i++)
            if(matrix[i][0] == '1'){
                dp[i][0] = 1;
                ans = 1;
            }
        for(int j = 0; j < n; j++)
            if(matrix[0][j] == '1'){
                dp[0][j] = 1;
                ans = 1;
            }
        for(int i = 1; i < m; i++)
            for(int j = 1; j < n; j++)
                if(matrix[i][j] == '1'){
                    dp[i][j] = min(dp[i-1][j], min(dp[i-1][j-1], dp[i][j-1])) + 1;
                    ans = max(ans, dp[i][j]);
                }
                else
                    dp[i][j] = 0;
        return ans*ans;
    }
};