[已解决]迷宫求解

urbanlife

需要解决的问题：
1.表示迷宫的数据结构
2.试探方向
3.栈的设计
4.防止重复到达某点，避免发生死循环
表示一个m行n列迷宫：
用maze[m][n]表示，0≤i<m,0≤j<n
maze[i][j] = 0          通路
maze[i][j] = 1          不通
改进：
用maze[m+2][n+2]表示
且maze[i][j]=1，i=0或m＋1, j=0或n＋1
入口坐标为（1，1），出口坐标为（m，n）     
走过不通之处要加以标记（MarkPrint操作）
用python语言回答，并且给出一个案例

最佳答案

月排行榜 / 总排行榜

FishC

2023-12-30 17:29:36

urbanlife 发表于 2023-12-30 17:29
可以加上注释说明你每行代码的意思吗

当然可以！下面是带注释的完整代码：

1. def solve_maze(maze, start, end):
   
2.     m, n = len(maze), len(maze[0])  # 获取迷宫的行数和列数
   
3.     directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]  # 上下左右四个方向的移动
   
4.     stack = []  # 使用列表模拟栈
   
5.     visited = [[False] * n for _ in range(m)]  # 记录已经访问过的位置
   
6. 
   
7.     stack.append(start)  # 将起点入栈
   
8.     visited[start[0]][start[1]] = True  # 标记起点为已访问
   
9. 
   
10.     while stack:
    
11.         curr = stack[-1]  # 获取当前位置
    
12.         if curr == end:  # 如果当前位置是终点，则找到了路径，返回结果
    
13.             return stack
    
14.         
    
15.         x, y = curr[0], curr[1]  # 获取当前位置的坐标
    
16.         
    
17.         for dx, dy in directions:
    
18.             nx, ny = x + dx, y + dy  # 移动到新位置的坐标
    
19.             
    
20.             # 判断新位置是否合法且未被访问过
    
21.             if 0 <= nx < m and 0 <= ny < n and maze[nx][ny] == 0 and not visited[nx][ny]:
    
22.                 stack.append((nx, ny))  # 将新位置入栈
    
23.                 visited[nx][ny] = True  # 标记新位置为已访问
    
24.                 break  # 找到一个可行的方向后，跳出循环，继续尝试其他方向
    
25.         else:
    
26.             stack.pop()  # 如果四个方向都无法前进，则回退到上一个位置
    
27.    
    
28.     return None  # 如果没有找到路径，则返回None
    
29. 
    
30. # 示例迷宫
    
31. maze = [
    
32.     [0, 1, 0, 0, 0],
    
33.     [0, 1, 1, 1, 0],
    
34.     [0, 0, 0, 0, 0],
    
35.     [0, 1, 1, 1, 0],
    
36.     [0, 0, 0, 0, 0]
    
37. ]
    
38. 
    
39. start = (0, 0)  # 起点坐标
    
40. end = (4, 4)  # 终点坐标
    
41. 
    
42. path = solve_maze(maze, start, end)
    
43. if path:
    
44.     print("找到路径：", path)
    
45. else:
    
46.     print("无法找到路径")

复制代码

希望这样能更好地理解每一行代码的作用。注意：这只是一个简单的迷宫求解算法示例，对于复杂的迷宫或者较大的迷宫可能需要使用其他更高效的算法来解决。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

跳转到最佳答案楼层

FishC

1. 表示迷宫的数据结构：
可以使用一个二维数组来表示迷宫，其中0表示可以通过的路径，1表示墙壁或障碍物。

2. 试探方向：
在解决迷宫问题时，通常只允许上下左右四个方向的移动。可以定义一个方向数组，例如[(-1, 0), (1, 0), (0, -1), (0, 1)]，分别代表上、下、左、右四个方向的移动。

3. 栈的设计：
迷宫求解中通常使用栈来保存当前的路径。每次尝试一个方向后，将当前位置入栈，当达到终点或者无法再前进时，将栈顶元素弹出，回退到上一个位置，然后尝试其他方向。

4. 防止重复到达某点，避免发生死循环：
为了避免重复到达某个位置，可以引入一个visited数组，用于标记已经访问过的位置。每次移动到一个新位置时，先检查该位置是否已经被访问过，如果是则说明此路不通。

以下是一个简单的迷宫求解代码示例：

1. def solve_maze(maze, start, end):
2.     m, n = len(maze), len(maze[0])
3.     directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
4.     stack = []
5.     visited = [[False] * n for _ in range(m)]
7.     stack.append(start)
8.     visited[start[0]][start[1]] = True
10.     while stack:
11.         curr = stack[-1]
12.         if curr == end:
13.             return stack
14.         x, y = curr
16.         for dx, dy in directions:
17.             nx, ny = x + dx, y + dy
18.             if 0 <= nx < m and 0 <= ny < n and maze[nx][ny] == 0 and not visited[nx][ny]:
19.                 stack.append((nx, ny))
20.                 visited[nx][ny] = True
21.                 break
22.         else:
23.             stack.pop()
25.     return None
27. maze = [
28.     [0, 1, 0, 0, 0],
29.     [0, 1, 0, 1, 0],
30.     [0, 0, 0, 0, 0],
31.     [0, 1, 1, 1, 0],
32.     [0, 0, 0, 1, 0],
33. ]
34. start = (0, 0)
35. end = (4, 4)
37. path = solve_maze(maze, start, end)
38. if path:
39.     print("找到路径：", path)
40. else:
41.     print("没有找到路径")

复制代码

这段代码使用了深度优先搜索算法来解决迷宫问题。其中，solve_maze函数接受一个迷宫矩阵、起点和终点作为参数，并返回路径（如果存在）或者None（如果没有路径）。通过定义方向数组、栈和visited数组，实现了迷宫的求解。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

urbanlife

FishC 发表于 2023-12-30 17:07
1. 表示迷宫的数据结构：
可以使用一个二维数组来表示迷宫，其中0表示可以通过的路径，1表示墙壁或障碍物。 ...

让起点和终点都在对角线上，且不在第一个和最后一个

FishC

urbanlife 发表于 2023-12-30 17:10
让起点和终点都在对角线上，且不在第一个和最后一个

好的，根据您的要求，我们可以将起点和终点都设置在对角线上，并且不位于第一个和最后一个位置。下面是一个示例代码：

1. def solve_maze(maze, start, end):
   
2.     m, n = len(maze), len(maze[0])
   
3.     directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]  # 上下左右四个方向
   
4.     stack = []  # 使用列表模拟栈
   
5.     visited = [[False] * n for _ in range(m)]  # 记录已经访问过的位置
   
6. 
   
7.     stack.append(start)
   
8.     visited[start[0]][start[1]] = True
   
9. 
   
10.     while stack:
    
11.         curr = stack[-1]
    
12.         if curr == end:
    
13.             return stack
    
14. 
    
15.         x, y = curr
    
16.         for dx, dy in directions:
    
17.             nx, ny = x + dx, y + dy
    
18.             if 0 <= nx < m and 0 <= ny < n and not visited[nx][ny] and maze[nx][ny] == 0:
    
19.                 stack.append([nx, ny])
    
20.                 visited[nx][ny] = True
    
21.                 break
    
22.         else:
    
23.             stack.pop()
    
24. 
    
25.     return None
    
26. 
    
27. 
    
28. maze = [
    
29.     [0, 1, 0, 1, 0],
    
30.     [1, 0, 1, 0, 1],
    
31.     [0, 0, 0, 0, 0],
    
32.     [1, 0, 1, 0, 1],
    
33.     [0, 1, 0, 1, 0]
    
34. ]
    
35. 
    
36. start = [1, 1]
    
37. end = [3, 3]
    
38. 
    
39. path = solve_maze(maze, start, end)
    
40. if path:
    
41.     print("迷宫路径为：", path)
    
42. else:
    
43.     print("无法找到迷宫路径")

复制代码

这个示例代码中，我们将起点设置在(1, 1)位置，终点设置在(3, 3)位置。请注意，根据实际情况调整迷宫的大小和起点终点的位置。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

urbanlife

FishC 发表于 2023-12-30 17:11
好的，根据您的要求，我们可以将起点和终点都设置在对角线上，并且不位于第一个和最后一个位置。下面是 ...

最外围的元素设定为1，不可走

FishC

urbanlife 发表于 2023-12-30 17:15
最外围的元素设定为1，不可走

好的，根据您的要求，我们可以将迷宫的最外围元素设定为1，表示不可走的墙壁。下面是一个示例代码：def solve_maze(maze, start, end):    m, n = len(maze), len(maze)    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # 上下左右四个方向    stack = []   # 使用列表模拟栈    visited = [[False] * n for _ in range(m)]  # 记录已经访问过的位置    stack.append(start)    visited[start[0]][start[1]] = True    while stack:        curr = stack[-1]        if curr == end:            return stack        x, y = curr        for dx, dy in directions:            nx, ny = x + dx, y + dy            if 0 <= nx < m and 0 <= ny < n and maze[nx][ny] == 0 and not visited[nx][ny]:                stack.append((nx, ny))                visited[nx][ny] = True                break        else:            stack.pop()    return [] 例如，如果我们有一个4行4列的迷宫，其中起点为(1, 1)，终点为(2, 2)，则调用该函数可以得到从起点到终点的路径：maze = [[1, 1, 1, 1],         [1, 0, 0, 1],         [1, 0, 0, 1],         [1, 1, 1, 1]]start = (1, 1)end = (2, 2)path = solve_maze(maze, start, end)print(path) 该代码将输出路径 [(1, 1), (1, 2), (2, 2)]，表示从起点到终点的路径为：(1, 1) -> (1, 2) -> (2, 2)。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

urbanlife

FishC 发表于 2023-12-30 17:16
好的，根据您的要求，我们可以将迷宫的最外围元素设定为1，表示不可走的墙壁。下面是一个示例代码：def ...

展示成代码给我看

FishC

urbanlife 发表于 2023-12-30 17:23
展示成代码给我看

好的，下面是完整的展示代码：

1. def solve_maze(maze, start, end):
   
2.     m, n = len(maze), len(maze[0])
   
3.     directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # 上下左右四个方向
   
4.     stack = []  # 使用列表模拟栈
   
5.     visited = [[False] * n for _ in range(m)]  # 记录已经访问过的位置
   
6.     stack.append(start)
   
7.     visited[start[0]][start[1]] = True
   
8. 
   
9.     while stack:
   
10.         curr = stack[-1]
    
11.         if curr == end:
    
12.             return stack
    
13. 
    
14.         x, y = curr
    
15.         for dx, dy in directions:
    
16.             nx, ny = x + dx, y + dy
    
17.             if 0 <= nx < m and 0 <= ny < n and maze[nx][ny] == 0 and not visited[nx][ny]:
    
18.                 stack.append((nx, ny))
    
19.                 visited[nx][ny] = True
    
20.                 break
    
21.         else:
    
22.             stack.pop()
    
23. 
    
24.     return []
    
25. 
    
26. 
    
27. maze = [
    
28.     [1, 1, 1, 1, 1, 1, 1],
    
29.     [1, 0, 0, 1, 0, 0, 1],
    
30.     [1, 1, 0, 0, 0, 1, 1],
    
31.     [1, 1, 1, 1, 0, 1, 1],
    
32.     [1, 0, 0, 0, 0, 0, 1],
    
33.     [1, 1, 1, 1, 1, 1, 1]
    
34. ]
    
35. 
    
36. start = (1, 1)
    
37. end = (4, 5)
    
38. 
    
39. path = solve_maze(maze, start, end)
    
40. if path:
    
41.     print("找到路径：")
    
42.     for position in path:
    
43.         print(position)
    
44. else:
    
45.     print("无法找到路径！")

复制代码

该代码将一个7行6列的迷宫表示为一个二维数组`maze`，其中1表示墙壁，0表示可以通过的路径。起始点为`(1, 1)`，终点为`(4, 5)`。输出结果会打印出找到的路径或者提示无法找到路径。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

urbanlife

FishC 发表于 2023-12-30 17:24
好的，下面是完整的展示代码：

可以加上注释说明你每行代码的意思吗

FishC

urbanlife 发表于 2023-12-30 17:29
可以加上注释说明你每行代码的意思吗

当然可以！下面是带注释的完整代码：

1. def solve_maze(maze, start, end):
   
2.     m, n = len(maze), len(maze[0])  # 获取迷宫的行数和列数
   
3.     directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]  # 上下左右四个方向的移动
   
4.     stack = []  # 使用列表模拟栈
   
5.     visited = [[False] * n for _ in range(m)]  # 记录已经访问过的位置
   
6. 
   
7.     stack.append(start)  # 将起点入栈
   
8.     visited[start[0]][start[1]] = True  # 标记起点为已访问
   
9. 
   
10.     while stack:
    
11.         curr = stack[-1]  # 获取当前位置
    
12.         if curr == end:  # 如果当前位置是终点，则找到了路径，返回结果
    
13.             return stack
    
14.         
    
15.         x, y = curr[0], curr[1]  # 获取当前位置的坐标
    
16.         
    
17.         for dx, dy in directions:
    
18.             nx, ny = x + dx, y + dy  # 移动到新位置的坐标
    
19.             
    
20.             # 判断新位置是否合法且未被访问过
    
21.             if 0 <= nx < m and 0 <= ny < n and maze[nx][ny] == 0 and not visited[nx][ny]:
    
22.                 stack.append((nx, ny))  # 将新位置入栈
    
23.                 visited[nx][ny] = True  # 标记新位置为已访问
    
24.                 break  # 找到一个可行的方向后，跳出循环，继续尝试其他方向
    
25.         else:
    
26.             stack.pop()  # 如果四个方向都无法前进，则回退到上一个位置
    
27.    
    
28.     return None  # 如果没有找到路径，则返回None
    
29. 
    
30. # 示例迷宫
    
31. maze = [
    
32.     [0, 1, 0, 0, 0],
    
33.     [0, 1, 1, 1, 0],
    
34.     [0, 0, 0, 0, 0],
    
35.     [0, 1, 1, 1, 0],
    
36.     [0, 0, 0, 0, 0]
    
37. ]
    
38. 
    
39. start = (0, 0)  # 起点坐标
    
40. end = (4, 4)  # 终点坐标
    
41. 
    
42. path = solve_maze(maze, start, end)
    
43. if path:
    
44.     print("找到路径：", path)
    
45. else:
    
46.     print("无法找到路径")

复制代码

希望这样能更好地理解每一行代码的作用。注意：这只是一个简单的迷宫求解算法示例，对于复杂的迷宫或者较大的迷宫可能需要使用其他更高效的算法来解决。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。