Java深度优先搜索

Question

请问“网络寻路”这个题目怎么利用深度优先搜索解决呀？这是2013年蓝桥杯的一道题目

Answer 1

让阿豪来帮你解答，本回答参考chatgpt3.5编写提供，如果还有疑问可以评论或留言

题意描述： 在一个迷宫中，从起点出发寻找一条路径到达终点，路径上不能经过障碍物（#）和已经走过的路（*）。每次只能向上下左右四个方向移动一步，求出一条可行的路径。 思路： 深度优先搜索是一种用于遍历或的系统数据结构的算法。 它沿着树的深度遍历树的节点，尽可能深地从根节点到子节点。 深度优先搜索遵循一条路到底，然后返回并尝试另一条路的方法，直到所有路径都被检查。 在该题目中，可以利用深度优先搜索求解。从起点开始搜索，每次向四个方向移动。如果该点是障碍物或已经走过，则返回上一个节点。如果到达终点，则输出路径。在搜索过程中，注意更新已经走过的路径的标记。 代码实现：

maze = []  # 迷宫
book = []  # 记录是否走过
flag = 0  # 结束标志
# 向四个方向移动
nexts = [(0, 1), (1, 0), (0, -1), (-1, 0)] 
# 深度优先搜索
def dfs(x, y, step):
    global flag
    if x == ex and y == ey:  # 到达目的地
        flag = 1  # 标记搜索结束
        print('->'.join(maze[row][:col] for row, col in route[:step] + [(x, y)]))  # 输出路径
        return
    for dx, dy in nexts:  # 按照上下左右的顺序尝试移动
        nx, ny = x + dx, y + dy
        if 0 <= nx < n and 0 <= ny < m and not book[nx][ny] and maze[nx][ny] != '#':
            book[nx][ny] = 1  # 标记为已走
            route[step] = (nx, ny)  # 记录路径
            dfs(nx, ny, step + 1)  # 递归搜索
            if flag:  # 搜索结束，直接返回
                return
            book[nx][ny] = 0  # 重置为未走
    return
n, m = map(int, input().split())
sx, sy, ex, ey = map(int, input().split())
for i in range(n):
    line = input().strip()
    maze.append(line)
    book.append([0] * m)
route = [(-1, -1)] * (n * m)  # 记录路径
book[sx][sy] = 1
route[0] = (sx, sy)
dfs(sx, sy, 1)
if not flag:
    print('不存在路径！')

输入示例：

8 8
2 2 7 5
########
#......#
#.#.##.#
#.#.#..#
#...##.#
#.#.#.#.
#.#.#..#
########

输出示例：

(2, 2)->(2, 3)->(2, 4)->(3, 4)->(4, 4)->(5, 4)->(5, 5)->(5, 6)->(4, 6)->(4, 5)->(3, 5)->(2, 5)->(2, 6)->(2, 7)->(3, 7)->(4, 7)->(5, 7)->(6, 7)->(6, 6)->(7, 6)->(7, 5)->(7, 4)->(7, 3)->(7, 2)->(6, 2)->(5, 2)->(4, 2)->(3, 2)->(3, 3)->(4, 3)->(5, 3)->(6, 3)->(6, 4)->(6, 5)->(存在路径！)