十四届蓝桥杯STEMA考试Python真题试卷第二套第五题

来源：十四届蓝桥杯STEMA考试Python真题试卷第二套编程第五题
本题属于迷宫类问题，适合用DFS算法解决，解析中给出了Python中 map() 和列表推导式的应用技巧。最后介绍了DFS算法的两种常见实现方式——递归实现、栈实现，应用场景——迷宫类问题、图的连通性、树的遍历、拓朴排序、排列组合，以及主要优缺点。

题目描述

有一个 N*M 的矩阵，且矩阵中的每个方格都有一个整数（0≤整数≤100），小蓝需要按照以下要求从矩阵中找出一条最长的移动路线，且输出最长路线的长度（1 个方格为 1 个长度）。

要求：
1.小蓝可以从矩阵中任意一个方格开始向它的上、下、左、右相邻的任意一个方格移动，且移动的路线不能有交叉；
2.小蓝每次所要移动到的方格中的整数都要小于当前所在方格中的整数（如当前所在的方格中的整数为 3，那么可以移动到数字为 0，1，2 的格子里，不可以移动到数字为 3，4，5…的格子里）；

例如：
N=3，M=3，矩阵方格如下：

最长路线为 4 -> 3 -> 2 -> 1，故路线长度为 4。

输入描述：
第一行输入两个正整数 N，M（1＜N≤1000，1＜M≤1000），N 表示矩阵的行数，M 表示矩阵的列数，两个正整数之间以一个空格隔开
第二行开始输入 N 行，每行包含 M 个整数（0≤每个整数≤100），表示每个方格中的整数，每个整数之间以一个空格隔开

输出描述：
输出一个整数，表示最长路线的长度

样例输入：

3 3
1 1 3
2 3 4
1 1 1

样例输出：

4

参考答案

def longestPath(matrix):
    rows, cols = len(matrix), len(matrix[0])
    max_length = 0

    def dfs(i, j, visited):
        # 1. 基本状态: 当前位置已经计入路径长度
        current_length = 1

        # 2. 定义四个移动方向: 上、下、左、右
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

        # 3. 遍历每个可能的移动方向
        for di, dj in directions:
            # 计算新位置的坐标
            ni, nj = i + di, j + dj

            # 4. 检查移动的合法性
            if (
                0 <= ni < rows                      # 检查行是否越界
                and 0 <= nj < cols                  # 检查列是否越界
                and (ni, nj) not in visited         # 检查是否已访问
                and matrix[ni][nj] < matrix[i][j]   # 检查数字是否更小
            ):
                # 5. 递归探索
                visited.add((ni, nj))   # 标记已访问

                # 计算包含当前位置的最长路径
                current_length = max(current_length, 1 + dfs(ni, nj, visited))
                visited.remove((ni, nj))            # 回溯，移除访问标记

        return current_length

    # 6. 遍历矩阵中的每个位置作为起点
    for i in range(rows):
        for j in range(cols):
            visited = {