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 0Return 4.
DP: If matrix[i][j] == 1, D[i][j] = min(D[i][j-1], D[i-1][j], D[i-1][j-1]) + 1;
class Solution { public: int maximalSquare(vector<vector<char>>& matrix) { int m = matrix.size(); if(0 == m) return 0; int n = matrix[0].size(); vector<vector<int>> D(m, vector<int>(n, 0)); int res = 0; for(int i=0;i<m;i++) { D[i][0] = matrix[i][0] - '0'; if(D[i][0] == 1) res = 1; } for(int i=0;i<n;i++) { D[0][i] = matrix[0][i] - '0'; if(D[0][i] == 1) res = 1; } for(int i=1;i<m;i++) { for(int j=1;j<n;j++) { if(matrix[i][j]-'0' == 1) { D[i][j] = min(D[i-1][j-1], min(D[i-1][j], D[i][j-1])) + 1; res = max(D[i][j], res); } } } return res*res; } };