forked from atul14357/Hacktoberfest1435
-
Notifications
You must be signed in to change notification settings - Fork 0
/
rat_maze.java
103 lines (87 loc) · 2.31 KB
/
rat_maze.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
/* Java program to solve Rat in
a Maze problem using backtracking */
public class RatMaze {
// Size of the maze
static int N;
/* A utility function to print
solution matrix sol[N][N] */
void printSolution(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();
}
}
/* A utility function to check
if x, y is valid index for N*N maze */
boolean isSafe(
int maze[][], int x, int y)
{
// if (x, y outside maze) return false
return (x >= 0 && x < N && y >= 0
&& y < N && maze[x][y] == 1);
}
/* This function solves the Maze problem using
Backtracking. It mainly uses solveMazeUtil()
to solve the problem. It returns false if no
path is possible, otherwise return true and
prints the path in the form of 1s. Please note
that there may be more than one solutions, this
function prints one of the feasible solutions.*/
boolean solveMaze(int maze[][])
{
int sol[][] = new int[N][N];
if (solveMazeUtil(maze, 0, 0, sol) == false) {
System.out.print("Solution doesn't exist");
return false;
}
printSolution(sol);
return true;
}
/* A recursive utility function to solve Maze
problem */
boolean solveMazeUtil(int maze[][], int x, int y,
int sol[][])
{
// if (x, y is goal) return true
if (x == N - 1 && y == N - 1
&& maze[x][y] == 1) {
sol[x][y] = 1;
return true;
}
// Check if maze[x][y] is valid
if (isSafe(maze, x, y) == true) {
// Check if the current block is already part of solution path.
if (sol[x][y] == 1)
return false;
// mark x, y as part of solution path
sol[x][y] = 1;
/* Move forward in x direction */
if (solveMazeUtil(maze, x + 1, y, sol))
return true;
/* If moving in x direction doesn't give
solution then Move down in y direction */
if (solveMazeUtil(maze, x, y + 1, sol))
return true;
/* If none of the above movements works then
BACKTRACK: unmark x, y as part of solution
path */
sol[x][y] = 0;
return false;
}
return false;
}
public static void main(String args[])
{
RatMaze rat = new RatMaze();
int maze[][] = { { 1, 0, 0, 0 },
{ 1, 1, 0, 1 },
{ 0, 1, 0, 0 },
{ 1, 1, 1, 1 } };
N = maze.length;
rat.solveMaze(maze);
}
}
// This code is contributed by Abhishek Shankhadhar