回溯法猎人问题py
时间: 2024-02-19 13:58:19 浏览: 17
好的,回溯法猎人问题的 Python 代码如下:
```python
def can_move(x, y, maze):
"""判断当前位置是否可以移动"""
if 0 <= x < len(maze) and 0 <= y < len(maze[0]) and maze[x][y] == 0:
return True
return False
def dfs(x, y, maze, visited):
"""深度优先搜索"""
if x == len(maze) - 1 and y == len(maze[0]) - 1:
return True
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)] # 可以移动的方向
for dx, dy in directions:
nx, ny = x + dx, y + dy
if can_move(nx, ny, maze) and (nx, ny) not in visited:
visited.add((nx, ny))
if dfs(nx, ny, maze, visited):
return True
visited.remove((nx, ny))
return False
def solve(maze):
"""解决问题"""
if not maze:
return False
visited = {(0, 0)} # 记录已经走过的位置
return dfs(0, 0, maze, visited)
```
其中,`can_move` 函数用于判断当前位置是否可以移动,`dfs` 函数用于进行深度优先搜索,`solve` 函数则是整个问题的解决函数,返回一个布尔值,表示是否能够到达终点。