P6301. 中庸行者

解题思路

本题数据规模较小，最多只有 **8 * 8 = 64 个点，因此可以使用 DFS 回溯** 的方式枚举出所有路径。

回溯过程中的关键问题

• 上下坡交替切换：在回溯函数中可以设置一个 布尔型标记 `isUp`，来表示下一步移动是 上坡 还是 下坡。
• `checkList` 的更新需要回滚：与常规的 DFS 不同，同一个点有可能通过不同路径反复走到，因此 checkList 的更新需要 回滚。
• 路径长度记录：需要用一个变量 path_len 来记录当前路径长度的变化，可以直接将 `path_len + 1` 作为回溯的参数传入。

回溯调用的入口

回溯调用的入口需要同时考虑 第一步是上坡还是下坡 的情况。因此，对于每一个特定的点 (i, j)，其回溯入口都需要调用两次，分别设置 isUp 为 True 和 False。

---

PS：中庸真的是华子的核心价值观呀，连做题都要中庸（。 PSS：本题是 2023 年华为秋招 的笔试题目，分值 200 分。

思路展开

代码的主体是一个带状态回滚的回溯函数 backtracking，外加双重循环枚举所有出发点。关键参数：(i, j) 是当前所在格子；checkList 是与地图同尺寸的访问标记数组；path_len 是从起点走到当前格子已完成的移动次数；isUp 是布尔标志，表示下一步必须上坡（True）还是必须下坡（False）。 每次进入回溯函数，先用 path_len 更新全局答案 ans——这样任何一条中途路径的长度都会被记录，不必等走到死路。然后枚举上下左右四个近邻 (ni, nj)：要求不越界、未访问过，且高度满足当前方向约束（isUp 时必须严格更高，否则必须严格更低）。满足则把该格标记为已访问，携带 path_len+1 和取反后的 isUp 递归下去——isUp 取反正是「上坡下坡必须交替」的实现；递归返回后把标记改回 0，让该格子还能出现在同一起点出发的其他路径中。 主程序对每个格子 (i, j) 重建一份 checkList 并标记起点本身，然后分别以「第一步上坡」「第一步下坡」各调用一次回溯入口，保证两种开局都被枚举。

复杂度分析

设地图为 m 行 n 列。回溯枚举的是所有满足高度交替约束的简单路径，路径条数最坏随格子数指数增长：搜索树深度最多 m*n，每层至多 3 个有效分支（不能立即走回来路，方向与访问约束还会进一步剪枝），再乘上 m*n 个起点和 2 种开局方向，最坏时间约为 O(m*n * 3^(m*n)) 量级，是指数级算法。正如上文所说，本题数据规模很小（最多 8×8 = 64 个格子），加上「严格交替上下坡」这一强剪枝，实际搜索空间远小于理论上界，可以在时限内完成。 空间复杂度为 O(m*n)：checkList 与地图同尺寸，递归栈深度不超过一条路径的长度，即至多 m*n。

边界与注意事项

• 答案统计的是「移动次数」而非经过的格子数：path_len 从 0 起步、每走一步加 1，起点本身不计入。
• 高度相同的相邻格子不可达：代码用严格大于、严格小于判断，等高一律跳过，与题面「不能移动到高度相同的格子」一致。
• 若地图上任何相邻格子都等高，所有回溯入口都迈不出第一步，ans 保持初始值 0 输出。
• 每换一个起点都重建 checkList 并把起点标记为已访问，防止路径绕回起点；同一起点的两次入口调用（先上坡、先下坡）互不干扰，因为每次回溯返回时标记都已回滚。