Как разбить квадратную матрицу на квадратные подматрицы?

Я пытаюсь создать программу, которая возвращает максимальную квадратную подматрицу 1 из квадратной матрицы 0 и 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];**
        }
    }

Меня очень смущает строка, выделенная звездами/жирным шрифтом, так как я думаю, что это строка, вызывающая проблему. Однако я не уверен, как это вызывает проблему.


java matrix submatrix
person Daveguy    schedule 13.01.2016    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Я думаю, что цикл, который вы ищете, таков: поскольку testSquare является квадратным, просто начните с него, убедитесь, что он пронумерован от 0 до k, затем найдите другие индексы матрицы - m никогда не превысит k, поскольку k является минимальным, поэтому он начинается с i и j и переходит к i+k и j+k макс.

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];
    }
}
person gpasch    schedule 13.01.2016