### 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.,  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 :