CODEWITHSUNDEEP
javarecursionmultidimensional-array
bmb
bmb

Reputation: 401

Using recursion to check surrounding cells

I am working on a problem where a 2D-array is given that is prepopulated with 'o' and blank space characters. I have a loop which iterates through the 2D-array, and once it comes across an 'o', it should call a recursive method that will recursively find surrounding cells (up, down, left, or right, not diagonal) that are also 'o', and it will give all the connecting cells the same label.

The code I have right now is problematic because it will only check 1 of the surrounding cells because I am not sure how to set up the recursive call.

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;
    }

}

The output expected from this would be:

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

The issue with my code is it will go through the if-statements and find one neighbor and return that cell. It won't go back and return the other surrounding cells. I am unsure how I can handle this recursive problem. I am also not sure what data-type the recursive method should be using.

Upvotes: 1

Views: 1029

Answers (1)

Tyler
Tyler

Reputation: 955

You are returning inside each if statement. What you want to do is if you have an adjacent cell, go through all 4 if statements. You should call nameGroups() in each if statement but don't return. When that recursive call returns, it means that cell finished its recursion, so you should continue and check other directions.

Solution: change all 4 return nameGroups(...) to just nameGroups

Try that

As for the return type, it always will be true as there is no return false statement, and you don't check the return type for true or false so it can get away with being a void method

Upvotes: 2

Related Questions