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

Input:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Output: 4

 

（参考LeetCode 221 Maximal Square）

思路：

dp[i][j] 代表在以i, j 这个点为右下角的正方形变成
若这一格的值是1， 则这个正方形的边长就是它的上面，左手边
和斜上的值的最小边长 + 1
因为如果有一边短了缺了
都构成不了正方形

 

代码：

 1  public int maximalSquare(char[][] matrix) {
 2         // corner case
 3         if (matrix == null || matrix.length == 0) return 0;
 4         int m = matrix.length;
 5         int n = matrix[0].length;
 6         int[][] dp = new int[m + 1][n + 1];
 7 
 8         int res = 0;
 9         for (int i = 1; i <= m; i++) {
10             for (int j = 1; j <= n; j++) {
11                 if (matrix[i - 1][j - 1] == '1') {
12                     dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
13                     res = Math.max(res, dp[i][j]);
14                 }
15             }
16         }
17         return res * res;
18     }