1 深度优先搜索（DFS）5题

设想我们现在以第一视角身处一个巨大的迷宫当中，没有上帝视角，没有通信设施，更没有热血动漫里的奇迹，有的只是四周长得一样的墙壁。于是，我们只能自己想办法走出去。如果迷失了内心，随便乱走，那么很可能被四周完全相同的景色绕晕在其中，这时只能放弃所谓的侥幸，而去采取下面这种看上去很盲目但实际上会很有效的方法。

以当前所在位置为起点，沿着一条路向前走，当碰到岔道口时，选择其中一个岔路前进如果选择的这个岔路前方是一条死路，就退回到这个岔道口，选择另一个岔路前进。如果岔路中存在新的岔道口，那么仍然按上面的方法枚举新岔道口的每一条岔路。这样，只要迷宫存在出口，那么这个方法一定能够找到它。可能有读者会问，如果在第一个岔道口处选择了一条没有出路的分支，而这个分支比较深，并且路上多次出现新的岔道口，那么当发现这个分支是个死分支之后，如何退回到最初的这个岔道口?其实方法很简单，只要让右手始终贴着右边的墙壁一路往前走，那么自动会执行上面这个走法，并且最终一定能找到出口。图 8-1 即为使用这个方法走一个简单迷宫的示例。

从图 8-1 可知，从起点开始前进，当碰到岔道口时，总是选择其中一条岔路前进(例如图中总是先选择最右手边的岔路)，在岔路上如果又遇到新的岔道口，仍然选择新岔道口的其中一条岔路前进，直到碰到死胡同才回退到最近的岔道口选择另一条岔路。也就是说，当碰到岔道口时，总是以“深度”作为前进的关键词，不碰到死胡同就不回头，因此把这种搜索的方式称为深度优先搜索(Depth First Search，DFS)。从迷宫的例子还应该注意到，深度优先搜索会走遍所有路径，并且每次走到死胡同就代表一条完整路径的形成。这就是说，深度优先搜索是一种枚举所有完整路径以遍历所有情况的搜索方法。

深度优先搜索 (DFS)可以使用栈来实现。但是实现起来却并不轻松，有没有既容易理解又容易实现的方法呢?有的——递归。现在从 DFS 的角度来看当初求解 Fibonacci 数列的过程。回顾一下 Fibonacci数列的定义: $F (0) = 1, F (1) = 1, F (n) = F (n - 1) + F (n - 2) (n \geq 2)$ 。可以从这个定义中挖掘到，每当将 F(n)分为两部分 F(n-1)与 F(n-2)时，就可以把 F(n)看作迷宫的岔道口，由它可以到达两个新的关键结点 F(n-1)与 F(n-2)。而之后计算 F(n-1)时，又可以把 F(n-1)当作在岔道口 F(n)之下的岔道口。既然有岔道口，那么一定有死胡同。很容易想象，当访问到 F(0)和 F(1)时，就无法再向下递归下去，因此 F(0)和 F(1)就是死胡同。这样说来，递归中的递归式就是岔道口，而递归边界就是死胡同，这样就可以把如何用递归实现深度优先搜索的过程理解得很清楚。为了使上面的过程更清晰，可以直接来分析递归图 (见图 4-3)：可以在递归图中看到，只要n > 1，F(n)就有两个分支，即把 F(n)当作岔道口；而当n为1或0时，F(1)与F(0)就是迷宫的死胡同，在此处程序就需要返回结果。这样当遍历完所有路径（从顶端的 F(4)到底层的所有 F(1)与 F(0)）后，就可以得到 F(4)的值。

因此，使用递归可以很好地实现深度优先搜索。这个说法并不是说深度优先搜索就是递归，只能说递归是深度优先搜索的一种实现方式，因为使用非递归也是可以实现 DFS 的思想的，但是一般情况下会比递归麻烦。不过，使用递归时，系统会调用一个叫系统栈的东西来存放递归中每一层的状态，因此使用递归来实现 DFS 的本质其实还是栈。

sy313: 迷宫可行路径数简单

https://sunnywhy.com/sfbj/8/1/313

现有一个 n*m 大小的迷宫，其中1表示不可通过的墙壁，0表示平地。每次移动只能向上下左右移动一格（不允许移动到曾经经过的位置），且只能移动到平地上。求从迷宫左上角到右下角的所有可行路径的条数。

输入

第一行两个整数 $n 、 m (2 \leq n \leq 5, 2 \leq m \leq 5)$ ，分别表示迷宫的行数和列数；

接下来 n 行，每行 m 个整数（值为0或1），表示迷宫。

输出

一个整数，表示可行路径的条数。

样例1

输入

输出

解释

假设左上角坐标是(1,1)，行数增加的方向为增长的方向，列数增加的方向为增长的方向。

可以得到从左上角到右下角有两条路径：

(1,1)=>(1,2)=>(1,3)=>(2,3)=>(3,3)
(1,1)=>(2,1)=>(3,1)=>(3,2)=>(3,3)

加保护圈，原地修改

python

dx = [-1, 0, 1, 0]
dy = [ 0, 1, 0, -1]

def dfs(maze, x, y):
    global cnt
    
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
            
        if maze[nx][ny] == 'e':
            cnt += 1
            continue
            
        if maze[nx][ny] == 0:
            maze[x][y] = 1
            dfs(maze, nx, ny)
            maze[x][y] = 0
    
    return
            
n, m = map(int, input().split())
maze = []
maze.append( [-1 for x in range(m+2)] )
for _ in range(n):
    maze.append([-1] + [int(_) for _ in input().split()] + [-1])
maze.append( [-1 for x in range(m+2)] )

maze[1][1] = 's'
maze[n][m] = 'e'

cnt = 0
dfs(maze, 1, 1)
print(cnt)

辅助visited空间

python

MAXN = 5
n, m = map(int, input().split())
maze = []
for _ in range(n):
    row = list(map(int, input().split()))
    maze.append(row)

visited = [[False for _ in range(m)] for _ in range(n)]
counter = 0

MAXD = 4
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def is_valid(x, y):
    return 0 <= x < n and 0 <= y < m and maze[x][y] == 0 and not visited[x][y]

def DFS(x, y):
    global counter
    if x == n - 1 and y == m - 1:
        counter += 1
        return
    visited[x][y] = True
    for i in range(MAXD):
        nextX = x + dx[i]
        nextY = y + dy[i]
        if is_valid(nextX, nextY):
            DFS(nextX, nextY)
    visited[x][y] = False

DFS(0, 0)
print(counter)

sy314: 指定步数的迷宫问题中等

https://sunnywhy.com/sfbj/8/1/314

现有一个 n*m 大小的迷宫，其中1表示不可通过的墙壁，0表示平地。每次移动只能向上下左右移动一格（不允许移动到曾经经过的位置），且只能移动到平地上。现从迷宫左上角出发，问能否在恰好第步时到达右下角。

输入

第一行三个整数 $n 、 m 、 k (2 \leq n \leq 5, 2 \leq m \leq 5, 2 \leq k \leq n * m)$ ，分别表示迷宫的行数、列数、移动的步数；

接下来行，每行个整数（值为0或1），表示迷宫。

输出

如果可行，那么输出Yes，否则输出No。

样例1

输入

输出

Yes

解释

假设左上角坐标是(1,1)，行数增加的方向为增长的方向，列数增加的方向为增长的方向。

可以得到从左上角到右下角的步数为4的路径为：(1,1)=>(2,1)=>(2,2)=>(2,3)=>(3,3)。

样例2

输入

输出

No

解释

由于不能移动到曾经经过的位置，因此无法在恰好第6步时到达右下角。

加保护圈，原地修改

python

dx = [-1, 0, 1, 0]
dy = [ 0, 1, 0, -1]

canReach = False
def dfs(maze, x, y, step):
    global canReach
    if canReach:
        return
    
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if maze[nx][ny] == 'e':
            if step==k-1:
                canReach = True
                return
            
            continue
            
        if maze[nx][ny] == 0:
            if step < k:
                maze[x][y] = -1
                dfs(maze, nx, ny, step+1)
                maze[x][y] = 0
    

n, m, k = map(int, input().split())
maze = []
maze.append( [-1 for x in range(m+2)] )
for _ in range(n):
    maze.append([-1] + [int(_) for _ in input().split()] + [-1])
maze.append( [-1 for x in range(m+2)] )

maze[1][1] = 's'
maze[n][m] = 'e'

dfs(maze, 1, 1, 0)
print("Yes" if canReach else "No")

辅助visited空间

python

MAXN = 5
n, m, k = map(int, input().split())
maze = []
for _ in range(n):
    row = list(map(int, input().split()))
    maze.append(row)

visited = [[False for _ in range(m)] for _ in range(n)]
canReach = False

MAXD = 4
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def is_valid(x, y):
    return 0 <= x < n and 0 <= y < m and maze[x][y] == 0 and not visited[x][y]

def DFS(x, y, step):
    global canReach
    if canReach:
        return
    if x == n - 1 and y == m - 1:
        if step == k:
            canReach = True
        return
    visited[x][y] = True
    for i in range(MAXD):
        nextX = x + dx[i]
        nextY = y + dy[i]
        if step < k and is_valid(nextX, nextY):
            DFS(nextX, nextY, step + 1)
    visited[x][y] = False

DFS(0, 0, 0)
print("Yes" if canReach else "No")

sy315: 矩阵最大权值中等

https://sunnywhy.com/sfbj/8/1/315

现有一个 n*m 大小的矩阵，矩阵中的每个元素表示该位置的权值。现需要从矩阵左上角出发到达右下角，每次移动只能向上下左右移动一格（不允许移动到曾经经过的位置）。求最后到达右下角时路径上所有位置的权值之和的最大值。

输入

第一行两个整数 $n 、 m (2 \leq n \leq 5, 2 \leq m \leq 5)$ ，分别表示矩阵的行数和列数；

接下来 n 行，每行 m 个整数（ $- 100 \leq 整数 \leq 100$ ），表示矩阵每个位置的权值。

输出

一个整数，表示权值之和的最大值。

样例1

输入

2 2
1 2
3 4

输出

解释

从左上角到右下角的最大权值之和为。

加保护圈，原地修改

python

dx = [-1, 0, 1, 0]
dy = [ 0, 1, 0, -1]

maxValue = float("-inf")
def dfs(maze, x, y, nowValue):
    global maxValue
    if x==n and y==m:
        if nowValue > maxValue:
            maxValue = nowValue
        
        return
  
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
  
        if maze[nx][ny] != -9999:
            tmp = maze[x][y]
            maze[x][y] = -9999
            nextValue = nowValue + maze[nx][ny]
            dfs(maze, nx, ny, nextValue)
            maze[x][y] = tmp
    

n, m = map(int, input().split())
maze = []
maze.append( [-9999 for x in range(m+2)] )
for _ in range(n):
    maze.append([-9999] + [int(_) for _ in input().split()] + [-9999])
maze.append( [-9999 for x in range(m+2)] )


dfs(maze, 1, 1, maze[1][1])
print(maxValue)

辅助visited空间

python

MAXN = 5
INF = float('inf')
n, m = map(int, input().split())
maze = []
for _ in range(n):
    row = list(map(int, input().split()))
    maze.append(row)

visited = [[False for _ in range(m)] for _ in range(n)]
maxValue = -INF

MAXD = 4
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def is_valid(x, y):
    return 0 <= x < n and 0 <= y < m and not visited[x][y]

def DFS(x, y, nowValue):
    global maxValue
    if x == n - 1 and y == m - 1:
        if nowValue > maxValue:
            maxValue = nowValue
        return
    visited[x][y] = True
    for i in range(MAXD):
        nextX = x + dx[i]
        nextY = y + dy[i]
        if is_valid(nextX, nextY):
            nextValue = nowValue + maze[nextX][nextY]
            DFS(nextX, nextY, nextValue)
    visited[x][y] = False

DFS(0, 0, maze[0][0])
print(maxValue)

鉴于求最短、最长的问题都能用heapq实现，在图搜索中搭配bfs尤其好用。给出用heapq的bfs实现。

python

import heapq


def max_path_sum(matrix):
    n, m = len(matrix), len(matrix[0])
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # 右，下，左，上

    # 使用最大堆，堆元素为 (-权值和, 当前行, 当前列, 已访问路径)
    max_heap = [(-matrix[0][0], 0, 0, {(0, 0)})]

    max_value = float('-inf')  # 用于记录全局最大值

    while max_heap:
        # 从堆中取出当前路径
        curr_sum, x, y, visited = heapq.heappop(max_heap)
        curr_sum = -curr_sum  # 恢复为正值

        # 如果到达右下角，更新最大值
        if x == n - 1 and y == m - 1:
            max_value = max(max_value, curr_sum)
            continue

        # 扩展当前节点的所有邻居
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < m and (nx, ny) not in visited:
                new_visited = visited.copy()
                new_visited.add((nx, ny))
                heapq.heappush(max_heap, (-(curr_sum + matrix[nx][ny]), nx, ny, new_visited))

    return max_value


n, m = map(int, input().split())
maze = []
for _ in range(n):
    row = list(map(int, input().split()))
    maze.append(row)

print(max_path_sum(maze))

路径状态管理实现正确的去重逻辑，每条路径在扩展时独立处理。
独立路径管理：
为每条路径单独存储访问的点集（visited），避免路径交叉污染。
每次扩展时复制当前路径的访问状态，确保不重复访问。
终止条件更新：
到达右下角时，直接更新全局最大值 max_value。
堆扩展逻辑：
对于未访问的点，动态维护新的路径和，并加入堆中。
输出验证
对于输入：
2 5
4 38 55 42 -21
-85 -45 76 49 39
程序输出为 282，路径为：
4 -> 38 -> 55 -> 42 -> 49 -> 39
复杂度分析
时间复杂度：
最坏情况下，每个点的路径状态都可能被扩展，复杂度为 $O ((n \times m) \times 2^{n \times m})$ ，由于 $n, m \leq 5$ ，可以接受。
空间复杂度：
由于堆存储路径状态，复杂度为 $O (2^{n \times m})$ 。

以下是使用 deque 替代 heapq 实现的代码：

python

from collections import deque

def max_path_sum(matrix):
    n, m = len(matrix), len(matrix[0])
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # 右，下，左，上

    # 使用队列，存储 (当前权值和, 当前行, 当前列, 已访问路径)
    queue = deque([(matrix[0][0], 0, 0, {(0, 0)})])

    max_value = float('-inf')  # 用于记录全局最大值

    while queue:
        # 从队列中取出当前路径
        curr_sum, x, y, visited = queue.popleft()

        # 如果到达右下角，更新最大值
        if x == n - 1 and y == m - 1:
            max_value = max(max_value, curr_sum)
            continue

        # 扩展当前节点的所有邻居
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < m and (nx, ny) not in visited:
                new_visited = visited.copy()
                new_visited.add((nx, ny))
                queue.append((curr_sum + matrix[nx][ny], nx, ny, new_visited))

    return max_value


# 读取输入
n, m = map(int, input().split())
maze = []
for _ in range(n):
    row = list(map(int, input().split()))
    maze.append(row)

# 输出结果
print(max_path_sum(maze))

复杂度分析
时间复杂度：
同样是 $O ((n \times m) \times 2^{n \times m})$ ，但 deque 操作比 heapq 更简单，适合小规模问题。
空间复杂度：
队列存储所有路径状态，复杂度为 $O (2^{n \times m})$ 。

sy316: 矩阵最大权值路径中等

https://sunnywhy.com/sfbj/8/1/316

现有一个 n*m 大小的矩阵，矩阵中的每个元素表示该位置的权值。现需要从矩阵左上角出发到达右下角，每次移动只能向上下左右移动一格（不允许移动到曾经经过的位置）。假设左上角坐标是(1,1)，行数增加的方向为增长的方向，列数增加的方向为增长的方向。求最后到达右下角时路径上所有位置的权值之和最大的路径。

输入

第一行两个整数 $n 、 m (2 \leq n \leq 5, 2 \leq m \leq 5)$ ，分别表示矩阵的行数和列数；

接下来 n 行，每行 m 个整数（ $- 100 \leq 整数 \leq 100$ ），表示矩阵每个位置的权值。

输出

从左上角的坐标开始，输出若干行（每行两个整数，表示一个坐标），直到右下角的坐标。

数据保证权值之和最大的路径存在且唯一。

样例1

输入

2 2
1 2
3 4

输出

1 1
2 1
2 2

解释

显然当路径是(1,1)=>(2,1)=>(2,2)时，权值之和最大，即 1+3+4 = 8。

样例2

输入

4 5
59 -62 -71 91 -12
-36 42 -32 -36 43
-68 -88 -94 -43 -39
48 -38 53 31 -92

输出

样例3

输入

3 4
-36 -10 -84 -28
12 94 95 22
61 -13 26 29

输出

DFS辅助visited空间

python

# 读取输入
n, m = map(int, input().split())
maze = [list(map(int, input().split())) for _ in range(n)]

# 定义方向
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # 右、下、左、上
visited = [[False] * m for _ in range(n)]  # 标记访问
max_path = []
max_sum = -float('inf')  # 最大权值初始化为负无穷

# 深度优先搜索
def dfs(x, y, current_path, current_sum):
    global max_path, max_sum

    # 到达终点，更新结果
    if (x, y) == (n - 1, m - 1):
        if current_sum > max_sum:
            max_sum = current_sum
            max_path = current_path[:]
        return

    # 遍历四个方向
    for dx, dy in directions:
        nx, ny = x + dx, y + dy

        # 检查边界和是否访问过
        if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny]:
            # 标记访问
            visited[nx][ny] = True
            current_path.append((nx, ny))

            # 递归搜索
            dfs(nx, ny, current_path, current_sum + maze[nx][ny])

            # 回溯
            current_path.pop()
            visited[nx][ny] = False

# 初始化起点
visited[0][0] = True
dfs(0, 0, [(0, 0)], maze[0][0])

# 输出结果
for x, y in max_path:
    print(x + 1, y + 1)

sy317: 迷宫最大权值中等

https://sunnywhy.com/sfbj/8/1/317

现有一个大小的迷宫，其中1表示不可通过的墙壁，0表示平地。现需要从迷宫左上角出发到达右下角，每次移动只能向上下左右移动一格（不允许移动到曾经经过的位置），且只能移动到平地上。假设迷宫中每个位置都有权值，求最后到达右下角时路径上所有位置的权值之和的最大值。

输入

第一行两个整数 $n 、 m (2 \leq n \leq 5, 2 \leq m \leq 5)$ ，分别表示矩阵的行数和列数；

接下来 n 行，每行个 m 整数（值为0或1），表示迷宫。

再接下来行，每行个整数（ $- 100 \leq 整数 \leq 100$ ），表示迷宫每个位置的权值。

输出

一个整数，表示权值之和的最大值。

样例1

输入

输出

解释：从左上角到右下角的最大权值之和为 1+4+7+8+9 = 29。

加保护圈，原地修改

python

dx = [-1, 0, 1, 0]
dy = [ 0, 1, 0, -1]

maxValue = float("-inf")
def dfs(maze, x, y, nowValue):
    global maxValue
    if x==n and y==m:
        if nowValue > maxValue:
            maxValue = nowValue
        
        return
  
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
  
        if maze[nx][ny] == 0:
            maze[nx][ny] = -1
            tmp = w[x][y]
            w[x][y] = -9999
            nextValue = nowValue + w[nx][ny]
            dfs(maze, nx, ny, nextValue)
            maze[nx][ny] = 0
            w[x][y] = tmp
    

n, m = map(int, input().split())
maze = []
maze.append( [-1 for x in range(m+2)] )
for _ in range(n):
    maze.append([-1] + [int(_) for _ in input().split()] + [-1])
maze.append( [-1 for x in range(m+2)] )

w = []
w.append( [-9999 for x in range(m+2)] )
for _ in range(n):
    w.append([-9999] + [int(_) for _ in input().split()] + [-9999])
w.append( [-9999 for x in range(m+2)] )


dfs(maze, 1, 1, w[1][1])
print(maxValue)

辅助visited空间

python

MAXN = 5
INF = float('inf')
n, m = map(int, input().split())
maze = [list(map(int, input().split())) for _ in range(n)]
w = [list(map(int, input().split())) for _ in range(n)]
visited = [[False] * m for _ in range(n)]
maxValue = -INF

MAXD = 4
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def is_valid(x, y):
    return 0 <= x < n and 0 <= y < m and not maze[x][y] and not visited[x][y]

def dfs(x, y, nowValue):
    global maxValue
    if x == n - 1 and y == m - 1:
        if nowValue > maxValue:
            maxValue = nowValue
        return
    visited[x][y] = True
    for i in range(MAXD):
        nextX = x + dx[i]
        nextY = y + dy[i]
        if is_valid(nextX, nextY):
            nextValue = nowValue + w[nextX][nextY]
            dfs(nextX, nextY, nextValue)
    visited[x][y] = False

dfs(0, 0, w[0][0])
print(maxValue)

1 深度优先搜索（DFS）5题 ​

sy313: 迷宫可行路径数 简单 ​

sy314: 指定步数的迷宫问题 中等 ​

sy315: 矩阵最大权值 中等 ​

sy316: 矩阵最大权值路径 中等 ​

sy317: 迷宫最大权值 中等 ​

1 深度优先搜索（DFS）5题

sy313: 迷宫可行路径数简单

sy314: 指定步数的迷宫问题中等

sy315: 矩阵最大权值中等

sy316: 矩阵最大权值路径中等

sy317: 迷宫最大权值中等