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
| from collections import deque # str为ida中使用快捷键[shift+e]提取到的数据, 如果提取的是string literal则加上引号视作字符串,如果是C array(decimal)则加上中括号视作列表 str = [
120, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 38, 38, 38, 38, 38, 38, 36, 36, 36, 36, 36, 36, 36, 36, 36, 38, 36, 38, 36, 36, 38, 36, 36, 38, 38, 38, 38, 38, 36, 36, 38, 36, 38, 36, 36, 36, 38, 38, 36, 36, 36, 36, 38, 36, 36, 38, 36, 36, 36, 38, 38, 38, 36, 36, 36, 36, 36, 38, 36, 36, 38, 36, 36, 36, 38, 36, 38, 38, 36, 38, 36, 36, 36, 36, 36, 38, 36, 36, 36, 38, 36, 38, 36, 36, 38, 38, 38, 36, 36, 36, 38, 38, 38, 38, 38, 36, 38, 38, 38, 38, 36, 38, 36, 36, 36, 36, 36, 36, 36, 36, 36, 38, 38, 38, 38, 38, 38, 36, 36, 36, 36, 36, 36, 36, 36, 36, 38, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 38, 38, 38, 38, 36, 36, 38, 38, 38, 36, 36, 36, 36, 36, 36, 38, 38, 38, 38, 38, 38, 38, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 38, 36, 36, 38, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 38, 36, 38, 36, 36, 36, 36, 36, 36, 36, 36, 36, 38, 38, 38, 38, 38, 38, 38, 38, 121 ] s = 0 # s用作索引访问str, 供下面tmp列表取值
# 分析题目后设置迷宫的行列 row = 15 # 设置二维迷宫行数 col = 15 # 设置二维迷宫列数
maze = [] for i in range(row): tmp = [] for j in range(col): tmp.append(str[s]) s += 1 maze.append(tmp) # 凑一行添加一行到迷宫中 print(maze) # 设置二维四向迷宫, 如果题目是多个小迷宫问题, 拆分多次调用脚本获取路径即可 path_len = 0x7fffffff # 如果题目未给出终点坐标,则一定会指定路径的长度,在此处修改路径长度并+1,否则请保留path_len的极大值 0x7fffffff
# 进行BFS寻找路径 def bfs(start, end, barrier): directions = [(0, 1), (1, 0), (0, -1), (-1, 0)] # 定义四个方向的移动 for i in range(len(maze)): # 获取起点和终点在列表中的索引 for j in range(len(maze[i])): if (maze[i][j] == start): start = (i, j) if (maze[i][j] == end): end = (i, j) # 以下均是bfs算法套路 queue = deque() queue.append((start, [start])) # (当前位置, 路径) visited = set() visited.add(start) while queue: position, path = queue.popleft() if position == end: return path elif len(path) == path_len: return path for d in directions: next_position = (position[0] + d[0], position[1] + d[1]) if 0 <= next_position[0] < len(maze) and 0 <= next_position[1] < len(maze[0]) and \ maze[next_position[0]][next_position[1]] != barrier and next_position not in visited: queue.append((next_position, path + [next_position])) visited.add(next_position) return None
# 执行BFS搜索并打印结果 if __name__ == '__main__': # maze[起点x坐标][起点y坐标] = 'S' #如果题目给了起点终点的坐标,在这里直接给起点和终点添加特征 # maze[终点x坐标][终点y坐标] = 'E'
path = bfs(120, 121, 36) # bfs函数传入参数代表起点、终点、障碍的特征(若题目给出的数据无特征, 手动添加特征即可, 通常障碍是1也有可能是0或其它字符如'#') print("移动路径坐标:", path) print("移动路径方位:", end='') for i in range(1, len(path)): x1, y1, x2, y2 = path[i - 1][0], path[i - 1][1], path[i][0], path[i][1] if (x1 > x2): # 上 print("w", end='') elif (x1 < x2): # 下 print("s", end='') elif (y1 > y2): # 左 print("a", end='') elif (y1 < y2): # 右 print("d", end='')
|