题目描述:
输入一个二维数组,其中的1表示墙壁,0表示可以走的路,只能横着走或竖着走,不能斜着走,要求编程序找出从左上角到右下角的最短路线。
【输入】
一个5 × 5的二维数组,表示一个迷宫。数据保证有唯一解。
【输出】
左上角到右下角的最短路径,格式如样例所示。
【输入样例】
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
【输出样例】
(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)
思路
广度优先遍历:用一个列表记录广度优先遍历的节点,每个节点设置一个前向索引记录该节点的父亲节点的位置
import numpy as np
class node:
def __init__(self, x, y, pre):
self.x = x
self.y = y
self.pre = pre
if __name__ == "__main__":
puzzle = [
[0, 1, 0, 1, 0],
[0, 0, 0, 1, 0],
[0, 1, 0, 0, 0],
[0, 0, 0, 1, 0],
]
visit = np.zeros(20).reshape(4, 5)
pre = 0
tail = 0
queue = [node(0, 0, -1)]
visit[0][0]=1
tail += 1
flag = 0
move = [(0, 1), (0, -1), (-1, 0), (1, 0)]
while(pre < tail):
cur = queue[pre]
for i in range(len(move)): # 移动
next_x = cur.x+move[i][0]
next_y = cur.y+move[i][1]
if next_x not in range(len(puzzle)) or next_y not in range(len(puzzle[0])): # 超出边界
continue
if not visit[next_x][next_y] and puzzle[next_x][next_y]==0: # 如果没有访问过且不为0
visit[next_x][next_y] = 1
queue.append(node(next_x, next_y, pre))
tail += 1
if next_x == len(puzzle)-1 and next_y == len(puzzle[0])-1: # 如果访问到尾节点,则终止
flag = 1
break
pre += 1
if flag == 1:
trace=[]
cur = queue[-1]
pre = cur.pre
while pre != -1:
trace.append((cur.x,cur.y))
cur = queue[pre]
pre = cur.pre
trace.append((0,0))
for item in trace[::-1]:
print(item)
当仅仅是求通路不要求最短也可以使用深度优先:一直按同一个方向进行遍历,当遇到不能继续访问的节点时进行回溯
import numpy as np
class Node:
def __init__(self, x, y):
self.x = x
self.y = y
self.dir = 1
def get_dir(self):
return self.dir
def change_dir(self):
self.dir += 1
def dfs(puzzle,end_x,end_y):
start_x = 0
start_y = 0
stack = [Node(start_x, start_y)]
while(stack):
node = stack[-1]
direction = node.get_dir()
x = node.x
y = node.y
puzzle[x][y] = 1 #避免重复访问该节点
if x == end_x and y == end_y:
return stack
if direction == 1:
if x+1 in range(len(puzzle)) and puzzle[x+1][y] == 0: #判断是否越界,以及是否可以经过
stack.append(Node(x+1, y))
node.change_dir() # 切换至下一个方向继续运行
continue
elif direction == 2:
if x-1 in range(len(puzzle)) and puzzle[x-1][y] == 0:
stack.append(Node(x-1, y))
node.change_dir()
continue
elif direction == 3:
if y+1 in range(len(puzzle[0])) and puzzle[x][y+1] == 0:
stack.append(Node(x, y+1))
node.change_dir()
continue
elif direction == 4:
if y-1 in range(len(puzzle[0])) and puzzle[x][y-1] == 0:
stack.append(Node(x, y-1))
node.change_dir()
continue
node=stack.pop() # 当direction大于等于4证明路径不可达
puzzle[node.x][node.y]=0 # 当前路径已经不包含该节点,解除该节点的不可访问锁,这样当回溯到这个节点时可以继续访问该节点的另一个方向
return None
if __name__ == "__main__":
puzzle = [
[0, 1, 0, 1, 0],
[0, 0, 0, 1, 0],
[0, 1, 0, 0, 0],
[0, 0, 0, 1, 0],
]
stack = dfs(puzzle, len(puzzle)-1, len(puzzle[0])-1)
for node in stack:
print((node.x,node.y))
网友评论