The Problem:

In the problem of the rat in a maze, a maze is given as N*N double dimensional array of blocks where source block is the upper left most block i.e., [0][0] and destination block is lower rightmost block i.e., [N-1][N-1]. A rat starts from source and has to reach the destination. The rat can move only in two directions: forward and down.

In the maze array, 0 means the block is a dead end and 1 means the block can be used in the path from source to destination.

The diagram of the maze is as below :

1 1 0 0
0 1 1 1
0 0 1 0
1 0 1 1

This is how the maze will look in array form.

The solution of the maze would look like this :

1 1 0 0
0 1 1 0
0 0 1 0
0 0 1 1

This is how the solution will look in array form after the code has been run.

To solve the problem, we will form a recursive function, which will follow a path and check if the path reaches the destination or not. If the path does not reach the destination then the function will backtrack and try other paths.

The Code:

public class Maze 
{ 
      static int N; 
  
      void printSol(int sol[][]) 
      { 
            for (int i = 0; i < N; i++) { 
                for (int j = 0; j < N; j++) 
                    System.out.print(" " + sol[i][j] + " "); 
                System.out.println(); 
            } 
      } 
  
    
        boolean isValid(int maze[][], int x, int y) 
        { 
            
            return (x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1); 
        } 
      
        
        boolean solMaze(int maze[][]) 
        { 
            int sol[][] = new int[N][N]; 
      
            if (solMazeUtil(maze, 0, 0, sol) == false) { 
                System.out.print("Solution doesn't exist"); 
                return false; 
            } 
      
            printSol(sol); 
            return true; 
        } 
      
       
        boolean solMazeUtil(int maze[][], int x, int y, 
                              int sol[][]) 
        { 
            
            if (x == N - 1 && y == N - 1 && maze[x][y] == 1) { 
                sol[x][y] = 1; 
                return true; 
            } 
      
            
            if (isValid(maze, x, y) == true) { 
                
                sol[x][y] = 1; 
      
                
                if (solMazeUtil(maze, x + 1, y, sol)) 
                    return true; 
      
                
                if (solMazeUtil(maze, x, y + 1, sol)) 
                    return true; 
      
                 
                
                sol[x][y] = 0; 
                return false; 
            } 
      
            return false; 
        } 
      
        public static void main() 
        { 
            Maze rat = new Maze(); 
            int maze[][] = {{ 1, 1, 0, 0 }, 
                            { 0, 1, 1, 1 }, 
                            { 0, 0, 1, 0 }, 
                            { 1, 0, 1, 1 } }; 
      
            N = maze.length; 
            rat.solMaze(maze); 
        } 
} 

This code has :

A time complexity of O(2n2  ).

A space complexity of O(n2 ).

The github link for the code is :

https://github.com/AdityaSareen06/java/blob/master/Maze.java

The picture has been taken from :

Business vector created by freepik – www.freepik.com

Visits: 82

Leave a Reply

Your email address will not be published. Required fields are marked *