This is one of the classicl problems of computer science. There is a rat trapped

Question

This is one of the classicl problems of computer science. There is a rat trapped in a maze. There are multiple paths in the maze from the starting point to the ending point. There is some cheese at the exit. The rat starts from the entrance of the maze and wants to get to the cheese. This problem can be attacked as follows: Have an m m matrix which represents the maze. For the sake of simplifying the implementation, have a boundary around your matrix and fill it up with all ones. This is so that you know when the rat is trying to go out of the boundary of the maze. In the real world, the rat would know not to go out of the maze, but hey! So, initially the matrix (I mean, the maze) would be something like (the ones represent the "extra" boundary we have added). The ones inside specify the obstacles. 100000000000000000001 100000010000000000001 100000010000000000001 100000000100001000001 100001000010000000001 100000000100000000001 100000000000000000001 The rat can move in four directions at any point in time (well, right, left, up, down). Please note that the rat can't move diagonally. Imagine a real maze and not a matrix, In matrix language

Explanation / Answer

The coordinates for down is missing in the question, I assumed it to {1,0} in the question and solved it.

public class RatInMaze {

   public int[][] solution;

   //initialize the solution matrix in constructor.
   public RatInMaze(int N) {
       solution = new int[N][N];
       for (int i = 0; i < N; i++) {
           for (int j = 0; j < N; j++) {
               solution[i][j] = 0;
           }
       }
   }

   public void solveMaze(int[][] maze, int N) {
       if (findPath(maze, 0, 0, N, "down")) {
           print(solution, N);
       }else{
           System.out.println("NO PATH FOUND");
       }
      
   }

   public boolean findPath(int[][] maze, int x, int y, int N, String direction) {
       // check if maze[x][y] is feasible to move
       if(x==N-1 && y==N-1){//we have reached
           solution[x][y] = 1;
           return true;
       }
       if (isSafeToGo(maze, x, y, N)) {
           // move to maze[x][y]
           solution[x][y] = 1;          
           // now rat has four options, either go right OR go down or left or go up
           if(direction!="up" && findPath(maze, x-1, y, N, "down")){ //go down
               return true;
           }
           //else go down
           if(direction!="left" && findPath(maze, x, y-1, N,"right")){ //go right
               return true;
           }
           if(direction!="down" && findPath(maze, x+1, y, N, "up")){ //go up
               return true;
           }
           if(direction!="right" && findPath(maze, x, y+1, N, "left")){ //go left
               return true;
           }
           //if none of the options work out BACKTRACK undo the move
           solution[x][y] = 0;
           return false;
       }
       return false;
   }

   // this function will check if mouse can move to this cell
   public boolean isSafeToGo(int[][] maze, int x, int y, int N) {
       // check if x and y are in limits and cell is not blocked
       if (x >= 0 && y >= 0 && x < N && y < N && maze[x][y] != 0) {
           return true;
       }
       return false;
   }
   public void print(int [][] solution, int N){
       for (int i = 0; i < N; i++) {
           for (int j = 0; j < N; j++) {
               System.out.print(" " + solution[i][j]);
           }
           System.out.println();
       }
   }
   public static void main(String[] args) {
       int N = 5;
       int[][] maze = { { 1, 1, 1, 0, 0 },
                       { 0, 0, 1, 1, 0 },
                       { 1, 0, 0, 1, 0 },
                       { 1, 1, 0, 1, 1 },
                       { 1, 1, 0, 0, 1 }
                       };
       RatInMaze r = new RatInMaze(N);
       r.solveMaze(maze, N);
   }

}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.