1.课题
给定一个列数为M，行数为N的方格棋盘。
棋盘上定义起点、终点、道路、墙壁。
棋盘上必有一个起点和一个终点，剩余方格必定为道路或者墙壁。
现寻求角色从起点到终点的最短路径长度，其中角色只能上下左右移动。
2.输入与输出
棋盘信息由文本文件提供。
第一行为列数M与行数N，由空格隔开。
第二行以后的N行，各为由空格隔开的M个字符。
其中，“s”代表起点，“g”代表终点，“0”代表道路，“1”代表墙壁。
通过标准输出，给出从起点到终点的最短长度。
如果不存在路径，则输出“Fail”。
3.基本思路
采用广度优先搜索思路(BFS)，从起点出发，计算起点到周围方格的举例，不断扩散范围直至找到终点。
定义一个队列，用于存储即将测量其最短路线长度的方格，然后把起点放入队列，并且初始化步数为1。
然后循环下列操作：
从队列中取出一个方格
该方格上下左右四个方格如果不是墙壁，加入队列
如果上下左右四个方格为终点，则直接输出步数作为结果，结束程序
步数加1
直至队列为空。
如果队列为空导致循环结束，则意味着没有路线能连接起点与终点，输出“Fail”。
4.Python实现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
59import collections
f = open("data.txt", "r")
input_line = f.readline()
input_line = input_line.strip('\n')
matrix_info = input_line.split(" ")
w = int(matrix_info[0])
h = int(matrix_info[1])
dirs = [(-1, 0), (0, 1), (1, 0), (0, -1)]
matrix = []
start_x = 0
start_y = 0
goal_x = 0
goal_y = 0
for i in range(0, h):
input_line = f.readline()
input_line = input_line.strip('\n')
row = input_line.split(" ")
for j in range(0, w):
if row[j] == 's':
start_x = j
start_y = i
matrix.append(row)
q = collections.deque()
q.append((start_x, start_y))
visited = set()
visited.add((start_x, start_y))
step = 1
flag = False
while q:
for _ in range(len(q)):
x, y = q.popleft()
for dx, dy in dirs:
nx, ny = x + dx, y + dy
if 0 <= nx < w and 0 <= ny < h and matrix[ny][nx] != '1' and (nx, ny) not in visited:
visited.add((nx, ny))
q.append((nx, ny))
if matrix[ny][nx] == 'g':
print(step, end='')
flag = True
break
if flag:
break
if flag:
break
step += 1
if not flag:
print('Fail', end='')
5.思考过程
最开始拿到这个问题的时候，直观想法是将棋盘抽象为无向图，每一个方格都看作是一个点，可以通行的点(起点、终点、道路)之间具有一条长度为1的边。
然后采用迪杰斯特拉算法求起点到终点的最短路径长度，采用Java实现。
但是在大规模数据上(大小为1000*1000的棋盘上)出现了Runtime Error。
因为是黑盒测试，所以不知道具体数据和错误信息。
因为其他普通数据(100*100以下的棋盘)没有问题，所以很难认为是数组越界等实现上的问题，可能还是数据规模过大导致的内存泄漏的原因。
于是更改思路，尝试了Python实现的A*算法，但是可能与其复杂的数据结构有关，大规模数据上出现了超时(16秒)的问题。
最后尝试了广度优先搜索，大规模数据在1.5秒以内运行完毕，成功通过所有测试数据。
6.相关问题
在调查的过程中，发现LeetCode上有一道十分类似的问题：1091. Shortest Path in Binary Matrix。
只不过这道问题里，角色还可以斜着移动，共有八个移动方向。
解决这个问题，只需要把向量集合改成八个方向就可以了。
1
2
3
4
5// 上下左右四个方向
dirs = [(-1, 0), (0, 1), (1, 0), (0, -1)]
// 上下左右+对角线八个方向
dirs = [(-1, -1), (-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1)]
7.测试数据
最后附上随机测试数据生成器：generator.py。
Reference Source: