CODEWITHSUNDEEP
javaarraysrecursionmatrix
Shadid
Shadid

Reputation: 4262

recursively finding an element in 2d matrix

I'm trying to find a number recursively in a matrix.

public class Test2 {
static char arry [][] = {{'#','#','#'},
                         {'#',' ',' '},
                         {'#',' ','#'},
                         {'#',' ','1'},
};

public static void main(String args []){
    recursion(2,1);

}

private static void recursion(int row, int col) {
    if(arry[row][col]=='1' && isInBound(row,col)==true){
        System.out.println("Found at " + row + " " + col);
    }else if ((isInBound(row,col)==true)&& arry[row][col]==' '){
        recursion(row,col+1);
        recursion(row,col-1);
        recursion(row-1,col);
        recursion(row+1,col);

    }

}

private static boolean isInBound(int row, int col) {
    boolean bol = false;
    if(row<= arry.length && col <= arry[0].length){
        bol = true;
    }

    return bol;
}

}

I'm trying to make the program in such way that I will be able to start from any positions. for example I'm starting from 2,1 position in this program. I'm getting a out of bounds exception. the code sometimes work for some inputs while using a try catch loop. I don't want to use a try catch unless absolutely necessary. I'm also trying to look for the in all 4 direction in the matrix. That's where my problem begins I'm going out of bound.

Upvotes: 1

Views: 2142

Answers (3)

Gee858eeG
Gee858eeG

Reputation: 185

this works:

public class Test2 {
    static char arry[][] = { { '#', '#', '#' }, { '#', ' ', ' ' },
            { '#', ' ', '#' }, { '#', ' ', '1' }, };
    static boolean[][] visited = new boolean[arry.length][arry[0].length];

    public static void main(String args[]) {
        // fill visited array
        for (int i = 0; i < visited.length; i++) {
            for (int j = 0; j < visited[0].length; j++) {
                visited[i][j] = false;
            }
        }

        recursion(2, 1);

    }

    private static void recursion(int row, int col) {
        if (!isInBound(row, col) || visited[row][col])
            return;
        visited[row][col] = true;

        if (arry[row][col] == '1') {
            System.out.println("Found at " + row + " " + col);
            return;
        } else if (arry[row][col] == ' ') {
            recursion(row, col + 1);
            recursion(row - 1, col);
            recursion(row + 1, col);
            recursion(row, col - 1);

        }

    }

    private static boolean isInBound(int row, int col) {
        boolean bol = false;
        if (row < arry.length && col < arry[0].length && col >= 0 && row >= 0) {
            bol = true;
        }

        return bol;
    }
}

Upvotes: 0

Michael Hagar
Michael Hagar

Reputation: 646

private static void recursion(int row, int col) {
    if(arry[row][col]=='1'){
        System.out.println("Found at " + row + " " + col);
    }
    else if (arry[row][col]=='#'){
        return;
    }
    if (isInBound(row,col + 1)){
        recursion(row,col+1);
    }
    if(isInBound(row, col - 1)){
        recursion(row, col - 1)
    }
    if(isInBound(row -1, col)){
        recursion(row-1,col);
    } 
    if(isInBound(row + 1, col) {
        recursion(row+1,col);
    }
    else {
        return;
    }
}

Assuming you're skipping #'s when you find one.

Upvotes: 0

ProgrammerDan
ProgrammerDan

Reputation: 901

Just using what you've written so far, you should check if your indexes are valid using isInBound first, and immediately return; if out of bounds. The way you are currently checking bounds, you will always use the bounds before you test them, meaning you're always going to encounter out of bounds exceptions, regardless of where you start.

E.g. at the beginning of private static void recursion(..), add the following:

if(!isInBound(row,col)) {
    return;
}

And no subsequent array bound test is necessary. Thus, any recursive call against an invalid bounds by your recursive calls will simply return without incurring an out of bounds exception.

Upvotes: 3

Related Questions