-
Notifications
You must be signed in to change notification settings - Fork 0
/
daily_coding_problem_23.test.js
141 lines (110 loc) · 3.25 KB
/
daily_coding_problem_23.test.js
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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
/*
This problem was asked by Google.
You are given an M by N matrix consisting of booleans that represents a board.
Each True boolean represents a wall. Each False boolean represents a tile you
can walk on.
Given this matrix, a start coordinate, and an end coordinate, return the
minimum number of steps required to reach the end coordinate from the start.
If there is no possible path, then return null. You can move up, left, down,
and right. You cannot move through walls. You cannot wrap around the edges of
the board.
For example, given the following board:
[[f, f, f, f],
[t, t, f, t],
[f, f, f, f],
[f, f, f, f]]
and start = (3, 0) (bottom left) and end = (0, 0) (top left), the minimum
number of steps required to reach the end is 7, since we would need to go
through (1, 2) because there is a wall everywhere else on the second row.
*/
const isDeepStrictEqual = require('util').isDeepStrictEqual
const shortestPath = (matrix, start, end) => {
if (!matrix || !matrix.length) return null
let result = 0
const queue = [start]
while (queue.length) {
const tempQueue = []
while (queue.length) {
const coordinate = queue.shift()
if (isDeepStrictEqual(coordinate, end)) return result
tempQueue.push(...nextHops(matrix, coordinate))
}
queue.push(...tempQueue)
result++
}
return null
}
const nextHops = (matrix, coordinate) => {
const n = matrix.length - 1
const m = matrix[0].length - 1
// -1 means already visited
matrix[coordinate[0]][coordinate[1]] = -1
const result = []
if (coordinate[0] + 1 <= n &&
matrix[coordinate[0] + 1][coordinate[1]] === 0) {
matrix[coordinate[0] + 1][coordinate[1]] = -1
result.push([coordinate[0] + 1, coordinate[1]])
}
if (coordinate[1] + 1 <= m &&
matrix[coordinate[0]][coordinate[1] + 1] === 0) {
matrix[coordinate[0]][coordinate[1] + 1] = -1
result.push([coordinate[0], coordinate[1] + 1])
}
if (coordinate[0] - 1 >= 0 &&
matrix[coordinate[0] - 1][coordinate[1]] === 0) {
matrix[coordinate[0] - 1][coordinate[1]] = -1
result.push([coordinate[0] - 1, coordinate[1]])
}
if (coordinate[1] - 1 >= 0 &&
matrix[coordinate[0]][coordinate[1] - 1] === 0) {
matrix[coordinate[0]][coordinate[1] - 1] = -1
result.push([coordinate[0], coordinate[1] - 1])
}
return result
}
// TESTS ///////////////////////////////////////////////////////////////////////
test('#1', () => {
const matrix = [
[0, 0, 0, 0],
[1, 1, 0, 1],
[0, 0, 0, 0],
[0, 0, 0, 0]
]
const start = [3, 0]
const end = [0, 0]
expect(shortestPath(matrix, start, end)).toBe(7)
})
test('#2', () => {
const matrix = [
[0, 0, 0, 0],
[0, 1, 1, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]
]
const start = [3, 2]
const end = [0, 2]
expect(shortestPath(matrix, start, end)).toBe(5)
})
test('#3', () => {
const matrix = [
[0, 0, 1, 0]
]
const start = [0, 0]
const end = [0, 3]
expect(shortestPath(matrix, start, end)).toBe(null)
})
test('#4', () => {
const matrix = [
[0, 0, 1, 0],
[1, 0, 1, 0]
]
const start = [1, 1]
const end = [1, 1]
expect(shortestPath(matrix, start, end)).toBe(0)
})
test('#5', () => {
const matrix = []
const start = [1, 1]
const end = [1, 1]
expect(shortestPath(matrix, start, end)).toBe(null)
})