广度优先搜索

0 1 2 3 4
0 0 1 0 0 0
1 0 0 0 1 0
2 0 1 0 1 0
3 1 1 1 0 0
4 0 1 0 0 1
5 0 1 0 0 0

按照“上左下右”的顺序进行探索。

0-(0, 0)

0 1 2 3 4
0 0 1
1 1
2 1 1
3 1 1 1
4 1 1
5 1

{$\varnothing$，$\varnothing$，(1, 0)，$\varnothing$}

$\text {Q}$：(1, 0)

1-(1, 0)

0 1 2 3 4
0 0 1
1 1 1
2 1 1
3 1 1 1
4 1 1
5 1

{$\varnothing$，$\varnothing$，(2, 0)，(1, 1)}

$\text {Q}$：(2, 0)，(1, 1)

2-(2, 0)

0 1 2 3 4
0 0 1
1 1 1
2 2 1 1
3 1 1 1
4 1 1
5 1

{$\varnothing$，$\varnothing$，$\varnothing$，$\varnothing$}

$\text {Q}$：(1, 1)

2-(1, 1)

0 1 2 3 4
0 0 1
1 1 2 1
2 2 1 1
3 1 1 1
4 1 1
5 1

{$\varnothing$，$\varnothing$，$\varnothing$，(1, 2)}

$\text {Q}$：(1, 2)

3-(1, 2)

0 1 2 3 4
0 0 1
1 1 2 3 1
2 2 1 1
3 1 1 1
4 1 1
5 1

{(0, 2)，$\varnothing$，(2, 2)，$\varnothing$}

$\text {Q}$：(0, 2)，(2, 2)

4-(0, 2)

0 1 2 3 4
0 0 1 4
1 1 2 3 1
2 2 1 1
3 1 1 1
4 1 1
5 1

{$\varnothing$，$\varnothing$，$\varnothing$，(0, 3)}

$\text {Q}$：(2, 2)，(0, 3)

4-(2, 2)

0 1 2 3 4
0 0 1 4
1 1 2 3 1
2 2 1 4 1
3 1 1 1
4 1 1
5 1

{$\varnothing$，$\varnothing$，$\varnothing$，$\varnothing$}

$\text {Q}$：(0, 3)

5-(0, 3)

0 1 2 3 4
0 0 1 4 5
1 1 2 3 1
2 2 1 4 1
3 1 1 1
4 1 1
5 1

{$\varnothing$，$\varnothing$，$\varnothing$，(0, 4)}

$\text {Q}$：(0, 4)

6-(0, 4)

0 1 2 3 4
0 0 1 4 5 6
1 1 2 3 1
2 2 1 4 1
3 1 1 1
4 1 1
5 1

{$\varnothing$，$\varnothing$，(1, 4)，$\varnothing$}

$\text {Q}$：(1, 4)

7-(1, 4)

0 1 2 3 4
0 0 1 4 5 6
1 1 2 3 1 7
2 2 1 4 1
3 1 1 1
4 1 1
5 1

{$\varnothing$，$\varnothing$，(2, 4)，$\varnothing$}

$\text {Q}$：(2, 4)

8-(2, 4)

0 1 2 3 4
0 0 1 4 5 6
1 1 2 3 1 7
2 2 1 4 1 8
3 1 1 1
4 1 1
5 1

{$\varnothing$，$\varnothing$，(3, 4)，$\varnothing$}

$\text {Q}$：(3, 4)

9-(3, 4)

0 1 2 3 4
0 0 1 4 5 6
1 1 2 3 1 7
2 2 1 4 1 8
3 1 1 1 9
4 1 1
5 1

{$\varnothing$，(3, 3)，$\varnothing$，$\varnothing$}

$\text {Q}$：(3, 3)

10-(3, 3)

0 1 2 3 4
0 0 1 4 5 6
1 1 2 3 1 7
2 2 1 4 1 8
3 1 1 1 10 9
4 1 1
5 1

{$\varnothing$，$\varnothing$，(4, 3)，$\varnothing$}

$\text {Q}$：(4, 3)

11-(4, 3)

0 1 2 3 4
0 0 1 4 5 6
1 1 2 3 1 7
2 2 1 4 1 8
3 1 1 1 10 9
4 1 11 1
5 1

{$\varnothing$，(4, 2)，(5, 3)，$\varnothing$}

$\text {Q}$：(4, 2)，(5, 3)

12-(4, 2)

0 1 2 3 4
0 0 1 4 5 6
1 1 2 3 1 7
2 2 1 4 1 8
3 1 1 1 10 9
4 1 12 11 1
5 1

{$\varnothing$，$\varnothing$，(5, 2)，$\varnothing$}

$\text {Q}$：(5, 3)，(5, 2)

12-(5, 2)

0 1 2 3 4
0 0 1 4 5 6
1 1 2 3 1 7
2 2 1 4 1 8
3 1 1 1 10 9
4 1 12 11 1
5 1 12

{$\varnothing$，$\varnothing$，$\varnothing$，(5, 4)}

$\text {Q}$：(5, 2)，(5, 4)

13-(5, 2)

0 1 2 3 4
0 0 1 4 5 6
1 1 2 3 1 7
2 2 1 4 1 8
3 1 1 1 10 9
4 1 12 11 1
5 1 13 12

{$\varnothing$，$\varnothing$，$\varnothing$，$\varnothing$}

$\text {Q}$：(5, 4)

13-(5, 4)

0 1 2 3 4
0 0 1 4 5 6
1 1 2 3 1 7
2 2 1 4 1 8
3 1 1 1 10 9
4 1 12 11 1
5 1 13 12 13

源代码

$\text {mazi.in}$：

1
2
3
4
5
6
7
6 5
0 1 0 0 0
0 0 0 1 0
0 1 0 1 0
1 1 1 0 0
0 1 0 0 1
0 1 0 0 0

$\text {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
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
package main

import (
	"fmt"
	"os"
)

func readMaze(filename string) [][]int {
	file, err := os.Open(filename)
	if err != nil {
		panic(err)
	}
	defer file.Close()
	var row, col int
	if _, err := fmt.Fscanf(file, "%d %d", &row, &col); err != nil {
		panic(err)
	}
	maze := make([][]int, row)
	for i := range maze {
		maze[i] = make([]int, col)
		for j := range maze[i] {
			if _, err := fmt.Fscanf(file, "%d", &maze[i][j]); err != nil {
				panic(err)
			}
		}
	}
	return maze
}

type point struct {
	i, j int
}

var dirs = [4]point{{-1, 0}, {0, -1}, {1, 0}, {0, 1}} // 上左下右

func (p point) add(dir point) point {
	return point{p.i + dir.i, p.j + dir.j}
}

func (p point) at(grid [][]int) (int, bool) {
	if p.i < 0 || p.i >= len(grid) {
		return 0, false
	}
	if p.j < 0 || p.j >= len(grid[0]) {
		return 0, false
	}
	return grid[p.i][p.j], true
}

func walk(maze [][]int, start, end point) [][]int {
	steps := make([][]int, len(maze))
	for i := range steps {
		steps[i] = make([]int, len(maze[0]))
		for j := range steps[i] {
			steps[i][j] = 0
		}
	}
	Q := []point{start}
	steps[start.i][start.j] = 0
	for len(Q) > 0 {
		cur := Q[0]
		Q = Q[1:]
		if cur == end {
			break
		}
		for _, dir := range dirs {
			next := cur.add(dir)
			val, ok := next.at(maze)
			if !ok {
				continue
			}
			if val == 1 {
				continue
			}
			val, ok = next.at(steps)
			if val > 0 {
				continue
			}
			if next == start {
				continue
			}
			curSteps, _ := cur.at(steps)
			steps[next.i][next.j] = curSteps + 1
			Q = append(Q, next)
		}
	}
	return steps
}

func main() {
	maze := readMaze("./maze/maze.in")
	for _, row := range maze {
		for _, col := range row {
			fmt.Printf("%3d", col)
		}
		fmt.Println()
	}
    fmt.Println()
	steps := walk(maze, point{0, 0}, point{len(maze) - 1, len(maze[0]) - 1})
	for _, row := range steps {
		for _, val := range row {
			fmt.Printf("%3d", val)
		}
		fmt.Println()
	}
}

0 1 0 0 0
0 0 0 1 0
0 1 0 1 0
1 1 1 0 0
0 1 0 0 1
0 1 0 0 0

0 0 4 5 6
1 2 3 0 7
2 0 4 0 8
0 0 0 10 9
0 0 12 11 0
0 0 13 12 13