Breaking
Backtracking

# Rat in a Maze

A Maze is given matrix and Rat start from upper left and should reach to lower right. The Rat starts from source to destination and moves only forward and down direction.

Given a maze, 4 x 4 matrix. A rat has to find a path from source to destination. Rat start from left top corner and go to right bottom destination. There are few cells which are dead end which means rat cannot enter into those cells.

Write a program to rat start from source to destination?

## source Code

```package com.dsacode.Algorithm.backtracking;

import java.util.Arrays;

public class RatinMaze {

public int[][] solution;

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) {

if(x==N-1 && y==N-1){
solution[x][y] = 1;
return true;
}
if (isSafeToGo(maze, x, y, N)) {
solution[x][y] = 1;

if(direction!="up" && findPath(maze, x+1, y, N, "down")){
return true;
}
if(direction!="left" && findPath(maze, x, y+1, N,"right")){
return true;
}
if(direction!="down" && findPath(maze, x-1, y, N, "up")){
return true;
}
if(direction!="right" &&  findPath(maze, x, y-1, N, "left")){
return true;
}

solution[x][y] = 0;
return false;
}
return false;
}

public boolean isSafeToGo(int[][] maze, int x, int y, int N) {
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, 0, 1, 1,1 },
{ 1, 1, 1, 0,1 },
{ 0, 0,0, 1, 1 },
{ 0, 0, 0, 1,0 },
{ 0, 0,0, 1, 1 } };

System.out.println("Arrays for Maze1 : "+ Arrays.deepToString(maze));

RatinMaze r = new RatinMaze(N);
r.solveMaze(maze, N);

int[][] maze2 = { { 1, 0, 1, 1,1 },
{ 1, 1, 1, 0,1 },
{ 0, 0,0, 1, 1 },
{ 0, 0, 0, 1,0 },
{ 0, 0,0, 0, 0 } };

System.out.println("Arrays for Maze2 : "+ Arrays.deepToString(maze2));

r.solveMaze(maze2, N);

}

}```

## Output

```Arrays for Maze1 : [[1, 0, 1, 1, 1], [1, 1, 1, 0, 1], [0, 0, 0, 1, 1], [0, 0, 0, 1, 0], [0, 0, 0, 1, 1]]
1 0 1 1 1
1 1 1 0 1
0 0 0 1 1
0 0 0 1 0
0 0 0 1 1
Arrays for Maze2 : [[1, 0, 1, 1, 1], [1, 1, 1, 0, 1], [0, 0, 0, 1, 1], [0, 0, 0, 1, 0], [0, 0, 0, 0, 0]]
NO PATH FOUND```