如何将正方形矩阵分解为正方形子矩阵？

Question

我想创建一个程序，从0和1的方阵返回1的最大方形子矩阵。现在我已经想出了如何将每个数字等于1开始的方形分成一个方形子矩阵。问题是，随着程序开始离矩阵的起点越远，它突然越界，我怀疑它是如何计算矩阵的哪一部分从每个子矩阵开始的。

这里是我的代码：

public static void main(String[] args) { 
    Scanner input = new Scanner(System.in); 
    System.out.print("Enter the number of rows and columns in the matrix (only one input, this is a square matrix): "); 
    int dimensions = input.nextInt(); 
    int[][] matrix = new int[dimensions][dimensions]; 
    for (int i = 0; i < matrix.length; i++) { 
     for (int j = 0; j < matrix[i].length; j++) { 
      int n = input.nextInt(); 
      if (n == 0 || n == 1) 
       matrix[i][j] = n; 
      else 
       System.out.print("Input only 0 or 1"); 
     } 
    } 
    int[] largestBlock = findLargestBlock(matrix); 
} 
public static int[] findLargestBlock(int[][] m) { 
    int[] solution = new int[3]; 
    //find rows with most consecutive 1's, then find columns with the same # of consecutive 1's 
    for (int i = 0; i < m.length; i++) { 
     for (int j = 0; j < m[i].length; j++) { 
      //"origin" for each iteration is (i, j) 
      if (m[i][j] == 1) 
       if (isSquare(m, i, j) == true) { 
        solution[0] = i; solution[1] = j; solution[2] = getSize(m, i, j); 
       } 
     } 
    } 
    return solution; 
} 
public static boolean isSquare(int[][] m, int i, int j) { 
    int k = m.length - i; 
    if (m[0].length - j < k) 
     k = m.length - j; 
    if (k < 2) 
     return false; 
    int[][] testSquare = new int[k][k]; 
    for (int y = i; y < m.length - i; y++) { 
     for (int x = j; x < m[i].length - j; x++) { 

      testSquare[y - i][x - j] = m[y][x]; 
     } 
    } 
    for (int y = 0; y < testSquare.length; y++) { 
     for (int x = 1; x < testSquare[y].length; x++) { 
      if (testSquare[y][x] != testSquare[y][x - 1]) 
       return false; 
     } 
    } 
    for (int x = 0; x < testSquare[0].length; x++) { 
     for (int y = 1; y < testSquare.length; y++) { 
      if (testSquare[y][x] != testSquare[y - 1][x]) 
       return false; 
     } 
    } 
    return true; 
} 

public static int getSize(int[][] m, int i, int j) { 
    int k = m.length - i; 
    if (m[0].length - j < k) 
     k = m.length - j; 
    return k; 
} 

我确定这部分程序是导致此问题，显然有它的一些缺陷，发送阵列的x或y值超出范围：

public static boolean isSquare(int[][] m, int i, int j) { 
    int k = m.length - i; 
    if (m[0].length - j < k) 
     k = m.length - j; 
    if (k < 2) 
     return false; 
    int[][] testSquare = new int[k][k]; 
    for (int y = i; y < m.length - i; y++) { 
     for (int x = j; x < m[i].length - j; x++) { 

      **testSquare[y - i][x - j] = m[y][x];** 
     } 
    } 

我很困惑星星/粗体字的行，因为我认为这是导致问题的线。但是，我不确定它是如何造成这个问题的。

Answer 1

我认为你正在寻找的循环是这样的 - 因为testSquare是正方形，只需从它开始，确保从0到k枚举，然后找到其他矩阵索引-m将永远不会超过k，因为k是最小值所以它从i和j开始，到达i + k和j + k max。

if (m[i].length - j < k) 
    k = m[i].length - j; 

for (int y = 0; y < k; y++) { 
    for (int x = 0; x < k; x++) { 

     testSquare[y][x] = m[i+y][j+x]; 
    } 
}