我正在尝试解决此代码问题，但无法做到-- 这段代码应该做 bfs 但它充当 dfs ？尝试求解器应该显示迷宫失败的尝试是一团糟，我无法解决。
我是初学者，只是想了解这里的问题。如果有人可以通过解释为我解决这个问题，我将不胜感激
import tkinter as tk
from queue import Queue
class MazeSolver:
def __init__(self, root, maze):
self.root = root
self.maze = maze
self.rows = len(maze)
self.cols = len(maze[0])
self.visited = [[False] * self.cols for _ in range(self.rows)]
self.solution = []
self.failed_attempt = []
self.canvas = tk.Canvas(root, width=self.cols * 30, height=self.rows * 30)
self.canvas.pack()
self.draw_maze()
self.solve_maze()
def draw_maze(self):
for i in range(self.rows):
for j in range(self.cols):
color = "white" if self.maze[i][j] == 0 else "black"
self.canvas.create_rectangle(
j * 30,
i * 30,
(j + 1) * 30,
(i + 1) * 30,
fill=color,
outline="black",
)
def solve_maze(self):
start = (0, 0)
end = (self.rows - 1, self.cols - 1)
queue = Queue()
queue.put([start]) # Enqueue the starting point as a path
while not queue.empty():
path = queue.get()
current = path[-1]
row, col = current
if current == end:
self.highlight_solution(path)
break
for move in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
new_row, new_col = row + move[0], col + move[1]
if (
0 <= new_row < self.rows
and 0 <= new_col < self.cols
and not self.visited[new_row][new_col]
and self.maze[new_row][new_col] == 0
):
new_path = list(path)
new_path.append((new_row, new_col))
queue.put(new_path)
self.visited[new_row][new_col] = True
def highlight_solution(self,path):
row, col = self.rows - 1, self.cols - 1
while (row, col) != (0, 0):
self.solution.append((row, col))
found_valid_move = False # Flag to check if a valid move is found
for move in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
new_row, new_col = row - move[0], col - move[1]
if (
0 <= new_row < self.rows
and 0 <= new_col < self.cols
and self.visited[new_row][new_col]
):
row, col = new_row, new_col
found_valid_move = True
break
if not found_valid_move:
# Handle the case where no valid move is found
break
self.solution.append((0, 0))
self.solution.reverse()
for step in path:
row, col = step
self.canvas.create_rectangle(
col * 30,
row * 30,
(col + 1) * 30,
(row + 1) * 30,
fill="yellow",
outline="black",
)
# Highlight cells from the failed attempt with a different color
for step in self.failed_attempt:
row, col = step
self.canvas.create_rectangle(
col * 30,
row * 30,
(col + 1) * 30,
(row + 1) * 30,
fill="red",
outline="black",
)
def main():
maze = [
[0, 1, 0, 0, 0],
[0, 0, 0, 1, 0],
[0, 1, 0, 1, 0],
[0, 1, 0, 0, 0],
[1, 1, 0, 1, 0],
]
root = tk.Tk()
root.title("Maze Solver")
MazeSolver(root, maze)
root.mainloop()
if __name__ == "__main__":
main()
看来您解决迷宫的代码大部分是正确的，但有几个问题需要解决。主要问题涉及处理highlight_solution函数和失败的尝试跟踪。
在这里，我修改了您的代码来解决这些问题。
import tkinter as tk
from queue import Queue
class MazeSolver:
def __init__(self, root, maze):
self.root = root
self.maze = maze
self.rows = len(maze)
self.cols = len(maze[0])
self.visited = [[False] * self.cols for _ in range(self.rows)]
self.solution = []
self.failed_attempt = []
self.canvas = tk.Canvas(root, width=self.cols * 30, height=self.rows * 30)
self.canvas.pack()
self.draw_maze()
self.solve_maze()
def draw_maze(self):
for i in range(self.rows):
for j in range(self.cols):
color = "white" if self.maze[i][j] == 0 else "black"
self.canvas.create_rectangle(
j * 30,
i * 30,
(j + 1) * 30,
(i + 1) * 30,
fill=color,
outline="black",
)
def solve_maze(self):
start = (0, 0)
end = (self.rows - 1, self.cols - 1)
queue = Queue()
queue.put([start]) # Enqueue the starting point as a path
while not queue.empty():
path = queue.get()
current = path[-1]
row, col = current
if current == end:
self.highlight_solution(path)
break
for move in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
new_row, new_col = row + move[0], col + move[1]
if (
0 <= new_row < self.rows
and 0 <= new_col < self.cols
and not self.visited[new_row][new_col]
and self.maze[new_row][new_col] == 0
):
new_path = list(path)
new_path.append((new_row, new_col))
queue.put(new_path)
self.visited[new_row][new_col] = True
def highlight_solution(self, path):
row, col = self.rows - 1, self.cols - 1
while (row, col) != (0, 0):
self.solution.append((row, col))
found_valid_move = False # Flag to check if a valid move is found
for move in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
new_row, new_col = row - move[0], col - move[1]
if (
0 <= new_row < self.rows
and 0 <= new_col < self.cols
and self.visited[new_row][new_col]
):
row, col = new_row, new_col
found_valid_move = True
break
if not found_valid_move:
# Handle the case where no valid move is found
self.failed_attempt.append((row, col)) # Track failed attempt
# Reverse the solution path to get it in the correct order
self.solution.reverse()
# Print the solution and failed attempt
print("Solution:", self.solution)
print("Failed Attempt:", self.failed_attempt)
if __name__ == "__main__":
maze = [
[0, 1, 0, 0, 0],
[0, 1, 0, 1, 0],
[0, 0, 0, 1, 0],
[1, 1, 1, 1, 0],
[0, 0, 0, 0, 0],
]
root = tk.Tk()
solver = MazeSolver(root, maze)
root.mainloop()
我在
found_valid_movehighlight_solutionfailed_attempt