[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.

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.

思路：

动态规划，用dp[i][j]代表从i,j的左上角到i,j形成的满足题意的正方形个数。

dp[i][j] = min( dp[i-1][j], dp[i-1][j-1], dp[i][j-1])+1.

int maximalSquare(vector<vector<char>>& matrix)
{
  int m = matrix.size(),n =matrix[0].size();
  if(m ==0)return 0;
  vector<vector<int>>dp(m,vector<int>(n,0));
  for(int i=0;i<n;i++)dp[0][i] = matrix[0][i] - '0';
  for(int i=0;i<m;i++)dp[i][0] = matrix[i][0] - '0';
  
  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][j-1],dp[i-1][j-1]))+1;     
    }
  }
  int size =0;
  for(int i=0;i<m;i++)
    for(int j =0;j<n;j++)
      size = max(size,dp[i][j]);
    
   return size*size;
}

参考：

http://www.cnblogs.com/jcliBlogger/p/4548751.html