Единица Площадь самой большой области единиц - PullRequest
Новая
       69

Единица Площадь самой большой области единиц

0 голосов
/ 18 июня 2020

Рассмотрим матрицу с N строками и M столбцами, где каждая ячейка содержит либо «0», либо «1», а любая ячейка, содержащая 1, называется заполненной ячейкой. Две ячейки называются связанными, если они примыкают друг к другу по горизонтали, вертикали или диагонали. Если одна или несколько заполненных ячеек соединены, они образуют область. Задача состоит в том, чтобы найти единицу площади самого большого региона.

Вот мой код: 

class GFG {
    static int max;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int t = 0; t < T; t++) {
            max = 1;
            int R = sc.nextInt();
            int C = sc.nextInt();
            int[][] M = new int[R][C];
            for (int i = 0; i < R; i++) {
                for (int j = 0; j < C; j++) {
                    M[i][j] = sc.nextInt();
                }
            }
            printMatrix(M, R, C);
            boolean[][] visited = new boolean[R][C];
            for (int i = 0; i < R; i++) {
                for (int j = 0; j < C; j++) {
                    int L = 1;
                    if (M[i][j] == 1 && !visited[i][j])
                        markVisited(M, visited, i, j, R, C, L);
                }
            }
            System.out.println(max);
        }
    }

    private static void printMatrix(int[][] M, int R, int C) {
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                System.out.print(M[i][j] + " ");
            }
            System.out.println();
        }

    }

    public static boolean isSafe(int[][] M, boolean[][] visited, int i, int j, int R, int C) {
        return ((i >= 0 && i < R) && (j >= 0 && j < C) && (M[i][j] == 1 && (!visited[i][j])));
    }

    public static void markVisited(int[][] M, boolean[][] visited, int x, int y, int R, int C, int L) {
        // int[] x_pos = {1 , 1, 1, 0, 0, -1, -1, -1};
        // int[] y_pos = {-1, 0, 1, -1, 1, -1, 0, 1};
        //commenting the arrays, as selecting one of the above and below combinations, result in different outputs
        int[] x_pos = { -1, -1, -1, 0, 0, 1, 1, 1 };
        int[] y_pos = { -1, 0, 1, -1, 1, -1, 0, 1 };

        visited[x][y] = true;
        for (int k = 0; k < 8; k++) {
            if (isSafe(M, visited, x + x_pos[k], y + y_pos[k], R, C)) {
                L++;
                max = Math.max(L, max);
                markVisited(M, visited, x + x_pos[k], y + y_pos[k], R, C, L);
            }
        }

    }
}

Код не работает для указанного ниже тестового примера: 1 4 7 1 1 1 1 0 0 1 1 0 1 0 1 1 0 0 0 0 0 1 0 1 1 0 0 0 1 1 1 вывод 13, ожидаемый 14. Интересно, что если я изменю x_pos и y_pos (закомментированные в коде) в методе markVisited как 

int[] x_pos = {1 , 1, 1, 0, 0, -1, -1, -1};  
int[] y_pos = {-1, 0, 1, -1, 1, -1, 0, 1};

, вывод будет 14. Я не понимаю, как вывод может измениться, если комбинации x_pos и y_pos одинаковы.
Это происходит и для других тестовых случаев. Я прокомментировал x_pos [] и y_pos [].
Пожалуйста, предложите, что не так.

Ответы [ 2 ]

1 голос
/ 18 июня 2020

Проблема в том, как вы накапливаете количество посещенных ячеек.

Сначала вам нужно изменить внешний l oop на: 

int max = 0;          
for (int i = 0; i < R; i++) {
    for (int j = 0; j < C; j++) {
        if (M[i][j] == 1 && !visited[i][j])
          max = Math.max(max, markVisited(M, visited, i, j, R, C));
    }
}
System.out.println(max);

Затем ваш markVisited метод должен возвращать количество посещенных ячеек, поэтому измените подпись на: 

public static int markVisited(int[][] M, boolean[][] visited, int x, int y, int R, int C)

Наконец, вам нужно накопить счетчик, когда вы рекурсивно переходите к соседям ячейки: 

int L = 1;
for (int k = 0; k < 8; k++) {
    if (isSafe(M, visited, x + x_pos[k], y + y_pos[k], R, C)) {           
        L += markVisited(M, visited, x + x_pos[k], y + y_pos[k], R, C);
    }
}
return L;

С этими изменениями вы получите желаемый результат, независимо от порядка, в котором вы посещаете соседи: 

1 1 1 1 0 0 1 
1 0 1 0 1 1 0 
0 0 0 0 1 0 1 
1 0 0 0 1 1 1 
14
1 голос
/ 18 июня 2020

Итак, ваша проблема в том, как вы рекурсивно накапливаете L. Вот ваш входной массив:

1 1 1 1 0 0 1

1 0 1 0 1 1 0

0 0 0 0 1 0 1

1 0 0 0 1 1 1

Как пример. Если путь, который вы уже накопили, разделен на два разных пути (давайте возьмем первые 3 строки вашего ввода для лучшего понимания)

1 1 1 1 0 0 1

1 0 1 0 1 1 0

0 0 0 0 1 0 1

В позиции (1, 5) вы можете go либо к 1 в правом верхнем углу, либо к 1 в внизу справа (ваш путь разделен на две части), вы передаете текущий L каждому из них, а затем каждый из этих путей накапливает L самостоятельно, вместо того, чтобы накапливать глобальный L, который предназначен для накопления всех найденных единиц который принадлежит основному пути, root которого - первая найденная вами 1.

Ваше исправление действительно простое, просто переместите L в начало ваших переменных, например: 

static int max;
static int L;

Затем вместо того, чтобы передавать L через ваши методы, просто сбрасывайте его значение каждый раз, когда вы запускаете новый root 1: 

if (M[i][j] == 1 && !visited[i][j]) {
    L = 1;
    markVisited(M, visited, i, j, R, C);
}

И, наконец, в вашем markVisited просто делайте то же самое, что и вы, но избавиться от этого параметра L в конце вашего метода, поскольку вы собираетесь использовать глобальный: 

max = Math.max(++L, max);

Надеюсь, это поможет, дайте мне знать, если это неясно, чтобы я мог добавить больше деталей, если необходимо ^ - ^

Стоит упомяните, что тот факт, что ваш код работает хорошо, если вы меняете переменные, является совпадением, потому что это поведение зависит от того, как вы go проходите через 1 в вашей итерации. В зависимости от того, какой из них вы выберете первым, вы можете либо упасть, либо нет, поэтому их изменение не является решением.

...