pls help me with this..Rat in Maze-1 problem

Anonymous User

13519

Consider a rat placed at (0, 0) in a square matrix of order N*N. It has to reach the destination at (N-1, N-1). Find all possible paths that the rat can take to reach from source to destination. The directions in which the rat can move are 'U'(up), 'D'(down), 'L' (left), 'R' (right). Value 0 at a cell in the matrix represents that it is blocked and cannot be crossed while value 1 at a cell in the matrix represents that it can be traveled through.

ERROR im facing is StackOverflow(Create BreakPoint).
but it works fine with 2 movements(down, right).

import java.util.ArrayList;

public class RatinMaze {
    public static void main(String args[]){
        int [][] maze={{1,1,1,1,1},
                {1,1,1,1,1},{1,1,1,1,1},
                {1,1,1,1,1},{1,1,1,1,1}};

        ArrayList<String> dir=new ArrayList<>();
		if(maze[0][0]==0||maze[maze.length-1][maze[0].length-1]==0){return dir;}
        Dfs(maze,0,0,dir,new ArrayList<>(),false,false,false,false);
        System.out.println(dir);
        return;
    }
    public static void Dfs(int[][] maze,int row,int col,ArrayList<String>dir,ArrayList<Character> d,boolean isUp,boolean isDown,boolean isLeft,boolean isRight){
        if(row<0||row>=maze.length||col<0||col>=maze[0].length||maze[row][col]==0){
            return;
        }
        if(row==maze.length-1 && col==maze[0].length-1){
            if(isUp){
                d.add('U');
            }else if(isDown){
                d.add('D');
            }else if(isLeft){
                d.add('L');
            }
            else if(isRight){
                d.add('R');
            }
            if(d.size()>0) {
                String s="";
                for(char c:d){
                    s+=c;
                }
                dir.add(s);
                s="";

            }
            System.out.println(d);
            d.remove(d.size()-1);
            return;


        }
        if(isUp){
            d.add('U');
        }else if(isDown){
            d.add('D');
        }else if(isLeft){
            d.add('L');
        }
        else if(isRight){
            d.add('R');
        }
        Dfs(maze, row-1, col, dir, d, true, false,false,false);
        Dfs(maze, row+1, col, dir, d, false, true,false,false);
        Dfs(maze, row, col-1, dir, d, false, false,true,false);
        Dfs(maze, row, col+1, dir, d, false, false,false,true);
        if(d.size()>0) {
            d.remove(d.size() - 1);
        }

    }
}

Comments (18)