1. /**
    2.  * Given an m x n binary matrix filled with 0's and 1's,
    3.  * find the largest square containing only 1's and return its area.
    4.  * <p>
    5.  * Example 1:
    6.  * Input: matrix = [
    7.  * ["1","0","1","0","0"],
    8.  * ["1","0","1","1","1"],
    9.  * ["1","1","1","1","1"],
    10.  * ["1","0","0","1","0"]
    11.  * ]
    12.  * Output: 4
    13.  * <p>
    14.  * Example 2:
    15.  * Input: matrix = [
    16.  * ["0","1"],
    17.  * ["1","0"]
    18.  * ]
    19.  * Output: 1
    20.  * <p>
    21.  * Example 3:
    22.  * Input: matrix = [
    23.  * ["0"]
    24.  * ]
    25.  * Output: 0
    26.  */
    27. public class Lesson221 {
    29.     static class Counter {
    31.         void test() {
    32.             Random random = new Random();
    33.             int rows = random.nextInt(10) + 1;
    34.             int cols = rows;
    35.             char[][] matrix = new char[cols][rows];
    37.             for (int i = 0; i < cols; i++) {
    38.                 for (int j = 0; j < rows; j++) {
    39.                     (matrix[i][j]) = Character.forDigit((int) (Math.random() + 0.5), 10);
    40.                 }
    41.             }
    43.             StringBuilder stringBuilder = new StringBuilder("[\n");
    45.             for (int i = 0; i < cols; i++) {
    46.                 for (int j = 0; j < rows; j++) {
    47.                     stringBuilder.append(matrix[i][j]);
    48.                     if (j < rows) {
    49.                         stringBuilder.append(",");
    50.                     }
    51.                 }
    52.                 if (i < cols) {
    53.                     stringBuilder.append("\n");
    54.                 }
    55.             }
    56.             stringBuilder.append("]");
    57.             System.out.println(stringBuilder);
    59.             int result = new Solution().maximalSquare(matrix);
    60.             System.out.println(result);
    61.         }
    63.     }
    65.     // 暴力破解
    66.     private static class Solution {
    68.         public int maximalSquare(char[][] matrix) {
    69.             int rows = matrix.length;
    70.             int cols = rows > 0 ? matrix[0].length : 0;
    71.             int maxsqlen = 0;
    72.             for (int i = 0; i < rows; i++) {
    73.                 for (int j = 0; j < cols; j++) {
    74.                     if (matrix[i][j] == '1') {
    75.                         int sqlen = 1;
    76.                         boolean flag = true;
    77.                         while (sqlen + i < rows && sqlen + j < cols && flag) {
    78.                             for (int k = j; k <= sqlen + j; k++) {
    79.                                 if (matrix[i + sqlen][k] == '0') {
    80.                                     flag = false;
    81.                                     break;
    82.                                 }
    83.                             }
    84.                             for (int k = i; k <= sqlen + i; k++) {
    85.                                 if (matrix[k][j + sqlen] == '0') {
    86.                                     flag = false;
    87.                                     break;
    88.                                 }
    89.                             }
    90.                             if (flag)
    91.                                 sqlen++;
    92.                         }
    93.                         if (maxsqlen < sqlen) {
    94.                             maxsqlen = sqlen;
    95.                         }
    96.                     }
    97.                 }
    98.             }
    99.             return maxsqlen * maxsqlen;
    100.         }
    103.     }
    105.     public static void main(String[] args) {
    106.         Counter counter = new Counter();
    107.         for (int i = 0; i < 10; i++) {
    108.             counter.test();
    109.             System.out.println("----------------------");
    110.         }
    112.     }
    115. }