Использование рекурсии для проверки окружающих клеток - PullRequest
Новая
       13

Использование рекурсии для проверки окружающих клеток

0 голосов
/ 11 ноября 2019

Я работаю над проблемой, где задан 2D-массив, который предварительно заполнен 'o' и пробелами. У меня есть цикл, который проходит через 2D-массив, и когда он встречает 'o', он должен вызвать рекурсивный метод, который будет рекурсивно находить окружающие ячейки (вверх, вниз, влево или вправо, а не по диагонали), которые также'o', и все соединительные ячейки получат одинаковую метку.

Код, который у меня есть сейчас, проблематичен, потому что он будет проверять только 1 из окружающих ячеек, потому что я не уверен, как настроить рекурсивный вызов. 

public class NameGroups {


    public static void main(String[] args) {
        char population[][] = {
                {'o','o','o',' ',' ',' ',' ',' ',' ',' '},
                {'o','o','o',' ',' ',' ',' ',' ','o','o'},
                {'o','o',' ',' ',' ',' ',' ',' ',' ',' '},
                {' ','o',' ',' ',' ',' ',' ',' ',' ',' '},
                {' ','o',' ',' ',' ','o',' ',' ',' ',' '},
                {' ',' ',' ',' ',' ','o','o',' ',' ',' '},
                {' ',' ',' ',' ',' ','o',' ',' ',' ',' '},
                {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '},
                {'o','o',' ',' ',' ',' ',' ',' ',' ',' '},
                {'o','o',' ',' ',' ',' ',' ',' ',' ',' '}
        };
        int groups = numberOfGroups(population);
        for (char[] line : population) {
            for (char item : line) {
                System.out.print(item);
            }
            System.out.println();
        }
        System.out.print("There are " + groups + " groups.");
    }

    public static int numberOfGroups(char[][] population) {
        int numGroups = 0;
        char name = '1';

        for(int row = 0; row < population.length; row++) {
            for(int col = 0; col < population[row].length; col++) {
                if(population[row][col] == 'o') {
                    nameGroups(population, name++, row, col);
                    numGroups++;
                }
            }
        }

        return numGroups;
    }

    private static boolean nameGroups(char[][] population, char name, int row, int col) {
        if (population[row][col] == 'o') {
            population[row][col] = name;
        }

        if(checkBounds(population, row + 1, col)) {
            if (population[row + 1][col] == '*') {
                return nameGroups(population, name, row + 1, col);
            }
        }

        if(checkBounds(population, row - 1, col)) {
            if (population[row - 1][col] == '*') {
                return nameGroups(population, name, row - 1, col);
            }
        }

        if(checkBounds(population, row, col + 1)) {
            if (population[row][col + 1] == '*') {
                return nameGroups(population, name, row, col + 1);
            }
        }

        if(checkBounds(population, row, col - 1)) {
            if (population[row][col - 1] == '*') {
                return nameGroups(population, name, row, col - 1);
            }
        }

        return true;
    }

    private static boolean checkBounds(char[][] population, int row, int col) {
        if(row < 0) {
            return false;
        } else if(col < 0) {
            return false;
        } else if(row >= population.length) {
            return false;
        } else if(col >= population[row].length) {
            return false;
        }

        return true;
    }

}

Выход ожидается отэто будет: 

        1,1,1, , , , , , , 
        1,1,1, , , , , ,2,2
        1,1, , , , , , , , 
         ,1, , , , , , , , 
         ,1, , , ,3, , , , 
         , , , , ,3,3, , , 
         , , , , ,3, , , , 
         , , , , , , , , , 
        4,4, , , , , , , , 
        4,4, , , , , , , ,

Проблема с моим кодом заключается в том, что он пройдет через операторы if, найдет одного соседа и вернет эту ячейку. Он не вернется и не вернет другие окружающие клетки. Я не уверен, как я могу справиться с этой рекурсивной проблемой. Я также не уверен, какой тип данных должен использовать рекурсивный метод.

1 Ответ

1 голос
/ 11 ноября 2019

Вы возвращаетесь внутри каждого оператора if. То, что вы хотите сделать, - это если у вас есть соседняя ячейка, пройти все 4 оператора if. Вы должны вызывать nameGroups () в каждом операторе if, но не возвращать. Когда этот рекурсивный вызов возвращается, это означает, что ячейка завершила свою рекурсию, поэтому вам следует продолжить и проверить другие направления.

Решение: измените все 4 return nameGroups(...) на nameGroups

Попробуйте

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

...