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 107 108 109 110 111 112 113 114 115 116 117 118 119
| from collections import deque
def is_valid_move(maze, visited, row, col): return (0 <= row < len(maze)) and (0 <= col < len(maze[0])) and (maze[row][col] == '0' and not visited[row][col])
def iterative_dfs(maze, start_row, start_col): stack = [(start_row, start_col, '')] visited = [[False] * len(maze[0]) for _ in range(len(maze))]
while stack: row, col, path = stack.pop() print(f"DFS访问: 行={row}, 列={col}, 路径={path}")
if (row, col) == (54, 74): return path
visited[row][col] = True directions = [(0, 1, 'd'), (1, 0, 's'), (0, -1, 'a'), (-1, 0, 'w')]
for dr, dc, direction in directions: new_row, new_col = row + dr, col + dc if is_valid_move(maze, visited, new_row, new_col): stack.append((new_row, new_col, path + direction))
return None
def bfs(maze): rows, cols = len(maze), len(maze[0]) queue = deque([(1, 1, '')]) visited = [[False] * cols for _ in range(rows)] visited[1][1] = True
directions = [(0, 1, 'd'), (1, 0, 's'), (0, -1, 'a'), (-1, 0, 'w')]
while queue: row, col, path = queue.popleft() print(f"BFS访问: 行={row}, 列={col}, 路径={path}")
if (row, col) == (54, 74): return path
for dr, dc, direction in directions: new_row, new_col = row + dr, col + dc if is_valid_move(maze, visited, new_row, new_col): visited[new_row][new_col] = True queue.append((new_row, new_col, path + direction))
return None
maze_str = """\ 11111111111111111111111111111111111111111111111111111111111111111111111111111111 10111111111111111110101010101000101001001001001001001111111111111111111111111111 10000000000000000011110100010100100101001001001010111000000000000000000011111111 11111111111111111011101111011010000111110010100101111011111111111111111011111111 11000000000000000011101111011010110111000000000000000011000000000000000011111111 11011111111111111111101111011010110111011111111111111111011111111111111111111111 11000000000000000011101111011010110111000000000000000011000000000000000011111111 11111111111111111011100001000010000111111111111111111011111111111111111011111111 11000000000000000011111111111111111111000000000000000011000000000000000011111111 11011111111111111111100001111100001111011111111111111111011111111111111111111111 11000000000000000011101111111101101111000000000000000011000000000011111000011111 11111111111111111011100001111100011111111111111111111011111111111011111011011111 11111111111111111011111101111101101111010010100101111011111111111011111011011111 11111111111111111001100001111100001111111111111111111011111111111011111011011111 10000000000000000100111111111111111110000000000000000010000000000011111011011111 10111111011111110110111111111111111110111111111111111110111111111111111011011111 10010110101010110110000000000000000010000000000000000010000000011111111011011111 10010110101010110111111111111111111011111111111111111011111111011111111011011111 10010101010010110111000000000000000011000000000000000011000000011111111011011111 10010101010010110111011111111111111111011111111111111111011111111111111011011111 10101010100101100111000000000000000011000000000000000011000000000000011011011111 10010010010101110111111111111111111011111111111111111011111111111111011011011111 10010010100101000111000000000000000011000000000000000011000000000000011011011111 10001010010010110111011111111111111111011111111111111111011111111111111011011111 10101110110101010111000000000000000011000000000000000011000000000000111011011111 10010101010010101111111111111111111011111111111111111011111111111110111011011111 10001010010010100100101001010000111011000000000000000011111111111110111011011111 10111111011111110111111111111111111000011111111111111111111111111110111011011111 11111111111111111111010101011101011111111111111111111111111111111110111011011111 10000000000000000011100011010101001101010010101010011000000000000000111011011111 10111111111111111011110101010001001011111111111111111011111111111111111011011111 10100000000000000011111111111111111111000000000000000011000000000000000011011111 10101111111111111111111111000000011111011111111111111111011111111111111111011111 10100000000000000011111111011111011111000000000000000011000000000000000011011111 10111111111111111011111111011111011111111111111111111011111111111111111011011111 10100000000000000011111111011111011111000000000000000011000000000000000011011111 10101111111111111111111111011111011111011111111111111111011111111111111111011111 10100000000000000011111111011111011111000000000000000011000000000000000011011111 10111111111111111011111111011111011111111111111111111011111111111111111011011111 10111100100010111011111111011111011111111111111111111011111111111111111011011111 10101001001001001001111111011111011111111111111111111011111111111111111001011111 10110010101000011100111111011111011110000000000000000010000000000000001101011111 10110001010100101110111111011111111110111111111111111110111111111111101101011111 10101010001000101110000000000000000010000000000000000010000000011111100001011111 10111101001010011111111111111111111011111111111111111011111111011111111111011111 10110010010100101011000000000000000011000000000000000011000000011111111111011111 10110100100101001011011111111111111111011111111111111111011111111111111111011111 10110010010010101011000000000000000011000000000000000011000000000000000011011111 10110010010100100101111111111111111011111111111111111011111111111111111011011111 10110010010101001101000000000000000011000000000000000011000000000000000011011111 10110010010100100101011111111111111111011111111111111111011111111111111111011111 10110010100100010011000000000000000000000000000000001111000000000000000011011111 10110000100010010111111111111111111111111111111111111000011111111111111011011111 10111100100100010001000011111111111000000000000000000011111111111111111011011111 10000000000000000000000000000000000011011111111111111110100101001000101001011111 """ maze = [list(row) for row in maze_str.strip().split('\n')]
print("DFS路径:") dfs_path = iterative_dfs(maze, 1, 1) print("BFS路径:") bfs_path = bfs(maze)
print(f"DFS最终路径: {dfs_path}") print(f"BFS最终路径: {bfs_path}")
|