-
Notifications
You must be signed in to change notification settings - Fork 2
/
1926_nearest_exit_from_entrance_maze.go
67 lines (57 loc) · 1.44 KB
/
1926_nearest_exit_from_entrance_maze.go
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
package leetcode
// https://leetcode.com/problems/nearest-exit-from-entrance-in-maze/description/
import "slices"
func nearestExit(maze [][]byte, entrance []int) int {
// exit is a zero byte
exit := byte(0)
n := len(maze)
// pad the maze
pad := make([]byte, n+2)
// pad top and bottom
maze = append(maze, pad)
maze = append([][]byte{pad}, maze...)
// pad left and right
for row := range maze {
maze[row] = append(maze[row], byte(0))
maze[row] = append([]byte{0}, maze[row]...)
}
entrance[0] += 1
entrance[1] += 1
queue := [][]int{entrance}
// fmt.Println(maze, queue)
stepCount := 0
// use BFS to find shortest path
for len(queue) > 0 {
size := len(queue)
for i := 0; i < size; i++ {
pos := queue[0]
queue = queue[1:]
if maze[pos[0]][pos[1]] == '+' {
continue
}
up := maze[pos[0]-1][pos[1]]
down := maze[pos[0]+1][pos[1]]
left := maze[pos[0]][pos[1]-1]
right := maze[pos[0]][pos[1]+1]
if !slices.Equal(pos, entrance) && (up == exit || down == exit || left == exit || right == exit) {
return stepCount
}
// mark as visited
maze[pos[0]][pos[1]] = '+'
if up == '.' {
queue = append(queue, []int{pos[0] - 1, pos[1]})
}
if down == '.' {
queue = append(queue, []int{pos[0] + 1, pos[1]})
}
if left == '.' {
queue = append(queue, []int{pos[0], pos[1] - 1})
}
if right == '.' {
queue = append(queue, []int{pos[0], pos[1] + 1})
}
}
stepCount++
}
return -1
}