LeetCode_221. 最大正方形

題目描述：

在一個由 0 和 1 組成的二維矩陣内，找到隻包含 1 的最大正方形，并傳回其面積。

輸入: 
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

輸出: 4      

思路：本題需要傳回矩陣中最大的正方形面積，計算正方形面積隻要知道邊長即可。申請一個跟matrix矩陣次元相同的數組，将數組的第一行和第一列初始化成matrix的第一行和第一列。

狀态轉移方程：$dp[i][j]=min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1 $ , ，對應于matrix[i][j]的正方形的最右下角元素。

狀态轉移方程的得到方法：試想2*2的正方形，如果要保證正方形必須要除了左上左上角都是1才能構成。

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        if(matrix.empty()||matrix[0].empty())
            return 0;
        int row=matrix.size();
        int col=matrix[0].size();
        vector<vector<int>> dp(row,vector<int>(col,0));
        int maxsqsize=0;//對于這個變量的指派需要注意
        for(int i=0;i<row;i++){
            dp[i][0]=matrix[i][0]-'0';
            maxsqsize=max(maxsqsize,dp[i][0]);//隻有一列的情況
        }
        for(int i=0;i<col;i++){
            dp[0][i]=matrix[0][i]-'0';
            maxsqsize=max(maxsqsize,dp[0][i]);//隻有一行的情況
        }
        //此雙層循環隻有矩陣的行列次元>=2才會執行
        for(int i=1;i<row;i++){
            for(int j=1;j<col;j++){
                if(matrix[i][j]=='1'){
                    dp[i][j]=min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
                    if(maxsqsize<dp[i][j])
                        maxsqsize=dp[i][j];
                }              
            }
        }
        return pow(maxsqsize,2);
    }
};      

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        if(matrix.empty()||matrix[0].empty())
            return 0;
        int row=matrix.size();
        int col=matrix[0].size();
        vector<vector<int>> dp(row+1,vector<int>(col+1,0));
        int maxsqsize=0;//多申請了一個單元，就不需要對這個元素做特别的處理了
        //這個雙層循環一定會執行
        for(int i=1;i<=row;i++){
            for(int j=1;j<=col;j++){
                if(matrix[i-1][j-1]=='1'){
                    dp[i][j]=min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
                    if(maxsqsize<dp[i][j])
                        maxsqsize=dp[i][j];
                }              
            }
        }
        return pow(maxsqsize,2);
    }
};