### 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(2^{n2 }).

A space complexity of O(n^{2} ).

The github link for the code is :

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

The picture has been taken from :