DFS算法避障python

DFS算法是一种用于遍历或搜索图或树的算法。它通过深入到图或树的最深层级，然后再回溯到上一层级来实现遍历或搜索的目的。在避障问题中，DFS算法可以用来找到从起点到终点的路径，同时避开障碍物。

下面是一个使用DFS算法来避障的Python示例代码：

def dfs(grid, start, end):
    rows = len(grid)
    cols = len(grid[0])
    visited = [[False] * cols for _ in range(rows)]
    path = []
    
    def backtrack(row, col):
        if row < 0 or row >= rows or col < 0 or col >= cols or grid[row][col] == 1 or visited[row][col]:
            return False
        
        visited[row][col] = True
        path.append((row, col))
        
        if (row, col) == end:
            return True
        
        if backtrack(row+1, col) or backtrack(row-1, col) or backtrack(row, col+1) or backtrack(row, col-1):
            return True
        
        path.pop()
        return False
    
    if backtrack(start[0], start[1]):
        return path
    else:
        return None

# 示例使用
grid = [
    [0, 0, 0, 0, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 0, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 0, 0]
]
start = (0, 0)
end = (4, 4)

result = dfs(grid, start, end)
if result:
    print("Path found:")
    for point in result:
        print(point)
else:
    print("No path found.")

这段代码中，我们使用了一个二维数组`grid`来表示迷宫，其中0表示可通行的空地，1表示障碍物。`start`和`end`分别表示起点和终点的坐标。函数`dfs`使用递归的方式进行深度优先搜索，通过回溯的方式找到从起点到终点的路径，并将路径保存在`path`列表中返回。