Rat in Maze Problem

In this problem, there is a given maze of size N x N. The source and the destination location is top-left cell and bottom right cell respectively. Some cells are valid to move and some cells are blocked. If one rat starts moving from start vertex to destination vertex, we have to find that is there any way to complete the path, if it is possible then mark the correct path for the rat.

The maze is given using a binary matrix, where it is marked with 1, it is a valid path, otherwise 0 for a blocked cell.

Note:The rat can move in top, left, right and bottom direction.

Implementation Using Java:

public class RatMaze {
	public static void ratInMaze(int maze[][])
	{
		int n=maze.length;
		int path[][]=new int[n][n];
		printPath(maze,0,0,path);
	}
	public static void printPath(int maze[][], int i, int j,int path[][])
	{
		int n=maze.length;
		if(i<0 || i>=n || j<0  ||j>=n || maze[i][j]==0 || path[i][j]==1)
		{
			return;
		}
		path[i][j]=1;
		if(i==n-1 && j==n-1)
		{
			for(int r=0;r<n;r++)
			{
				for(int c=0;c<n;c++)
				{
				System.out.print("The Path is:"+" "+path[r][c]+" ");
				}
				System.out.println();
			}
			path[i][j]=0;
			return;
		}
		printPath(maze,i-1,j,path);
		printPath(maze,i,j+1,path);
		printPath(maze,i+1,j,path);
		printPath(maze,i,j-1,path);
	}
	public static void main(String[] args) {
		int maze[][]= {{1,1,0},{1,1,0},{1,1,1}};
		ratInMaze(maze);
	}
}

---

Happy Coding!

Follow us on Instagram @programmersdoor

Join us on Telegram @programmersdoor

Please write comments if you find any bug in above code/algorithm, or find other ways to solve the same problem.

Follow Programmers Door for more.

#blog #interview #placement #learn #computer #science