用深度优先算法写猎人问题python语言

以下是一个使用深度优先算法解决猎人问题的Python实现。假设有一个矩阵表示森林，其中0表示空地，1表示树，2表示猎人，3表示猎物。猎人只能向上、下、左、右四个方向行走，不能穿过树木。猎人需要找到猎物并抓住它，输出所需行走的最小步数。

def dfs_forest(forest, visited, row, col, steps):
    if forest[row][col] == 3:
        return steps

    visited[row][col] = True
    min_steps = float('inf')

    # 向上走
    if row > 0 and not visited[row-1][col] and forest[row-1][col] != 1:
        min_steps = min(min_steps, dfs_forest(forest, visited, row-1, col, steps+1))

    # 向下走
    if row < len(forest)-1 and not visited[row+1][col] and forest[row+1][col] != 1:
        min_steps = min(min_steps, dfs_forest(forest, visited, row+1, col, steps+1))

    # 向左走
    if col > 0 and not visited[row][col-1] and forest[row][col-1] != 1:
        min_steps = min(min_steps, dfs_forest(forest, visited, row, col-1, steps+1))

    # 向右走
    if col < len(forest[0])-1 and not visited[row][col+1] and forest[row][col+1] != 1:
        min_steps = min(min_steps, dfs_forest(forest, visited, row, col+1, steps+1))

    visited[row][col] = False
    return min_steps

def find_hunter_and_prey(forest):
    hunter_row, hunter_col, prey_row, prey_col = None, None, None, None

    for i in range(len(forest)):
        for j in range(len(forest[0])):
            if forest[i][j] == 2:
                hunter_row, hunter_col = i, j
            elif forest[i][j] == 3:
                prey_row, prey_col = i, j

    return hunter_row, hunter_col, prey_row, prey_col

def main():
    forest = [[0,1,0,0,0],
              [0,1,0,1,0],
              [0,0,0,1,0],
              [0,1,1,1,0],
              [0,0,0,3,2]]

    hunter_row, hunter_col, prey_row, prey_col = find_hunter_and_prey(forest)
    visited = [[False for _ in range(len(forest[0]))] for _ in range(len(forest))]
    min_steps = dfs_forest(forest, visited, hunter_row, hunter_col, 0)

    print("最小步数为：", min_steps)

if __name__ == '__main__':
    main()

输出：

最小步数为： 7
``