forked from TheAlgorithms/JavaScript
- Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathRatInAMaze.js
More file actions
Latest commit
126 lines (105 loc) · 3.71 KB
/
Copy pathRatInAMaze.js
File metadata and controls
126 lines (105 loc) · 3.71 KB
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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
/*
* Problem Statement:
* - Given a NxN grid, find whether rat in cell [0, 0] can reach the target in cell [N-1, N-1]
* - The grid is represented as an array of rows. Each row is represented as an array of 0 or 1 values.
* - A cell with value 0 can not be moved through. Value 1 means the rat can move here.
* - The rat can not move diagonally.
*
* Reference for this problem: https://www.geeksforgeeks.org/rat-in-a-maze-backtracking-2/
*
* Based on the original implementation contributed by Chiranjeev Thapliyal (https://github.com/chiranjeev-thapliyal).
*/
/**
* Checks if the given grid is valid.
*
* A grid needs to satisfy these conditions:
* - must not be empty
* - must be a square
* - must not contain values other than {@code 0} and {@code 1}
*
* @param grid The grid to check.
* @throws TypeError When the given grid is invalid.
*/
functionvalidateGrid(grid){
if(!Array.isArray(grid)||grid.length===0)thrownewTypeError('Grid must be a non-empty array')
constallRowsHaveCorrectLength=grid.every(row=>row.length===grid.length)
if(!allRowsHaveCorrectLength)thrownewTypeError('Grid must be a square')
constallCellsHaveValidValues=grid.every(row=>{
returnrow.every(cell=>cell===0||cell===1)
})
if(!allCellsHaveValidValues)thrownewTypeError('Grid must only contain 0s and 1s')
}
functionisSafe(grid,x,y){
constn=grid.length
returnx>=0&&x<n&&y>=0&&y<n&&grid[y][x]===1
}
/**
* Attempts to calculate the remaining path to the target.
*
* @param grid The full grid.
* @param x The current X coordinate.
* @param y The current Y coordinate.
* @param solution The current solution matrix.
* @param path The path we took to get from the source cell to the current location.
* @returns {string|boolean} Either the path to the target cell or false.
*/
functiongetPathPart(grid,x,y,solution,path){
constn=grid.length
// are we there yet?
if(x===n-1&&y===n-1&&grid[y][x]===1){
solution[y][x]=1
returnpath
}
// did we step on a 0 cell or outside the grid?
if(!isSafe(grid,x,y))returnfalse
// are we walking onto an already-marked solution coordinate?
if(solution[y][x]===1)returnfalse
// none of the above? let's dig deeper!
// mark the current coordinates on the solution matrix
solution[y][x]=1
// attempt to move right
constright=getPathPart(grid,x+1,y,solution,path+'R')
if(right)returnright
// right didn't work: attempt to move down
constdown=getPathPart(grid,x,y+1,solution,path+'D')
if(down)returndown
// down didn't work: attempt to move up
constup=getPathPart(grid,x,y-1,solution,path+'U')
if(up)returnup
// up didn't work: attempt to move left
constleft=getPathPart(grid,x-1,y,solution,path+'L')
if(left)returnleft
// no direction was successful: remove this cell from the solution matrix and backtrack
solution[y][x]=0
returnfalse
}
functiongetPath(grid){
// grid dimensions
constn=grid.length
// prepare solution matrix
constsolution=[]
for(leti=0;i<n;i++){
constrow=Array(n)
row.fill(0)
solution[i]=row
}
returngetPathPart(grid,0,0,solution,'')
}
/**
* Creates an instance of the "rat in a maze" based on a given grid (maze).
*/
exportclassRatInAMaze{
constructor(grid){
// first, let's do some error checking on the input
validateGrid(grid)
// attempt to solve the maze now - all public methods only query the result state later
constsolution=getPath(grid)
if(solution!==false){
this.path=solution
this.solved=true
}else{
this.path=''
this.solved=false
}
}
}