企业官网建设流程全解析

1. 先把这个题彻底看明白：LintCode 258 到底在问什么

刷过 LintCode 的朋友应该对这类二维数组题目不陌生，但258 · 地图跳跃这道题和普通的矩阵遍历、动态规划不太一样，它考察的其实是图论里的单源最短路径问题，只不过换了一张“地图”的皮。拿到这个题目，第一眼看到的函数签名是这样的：

public int mapJump(int[][] arr)

输入一个二维数组arr，每一个格子存的是一个非负整数，表示从这个格子能跳跃的最大步数。你从左上角(0,0)出发，目标是跳到右下角(n-1, m-1)，每一步可以在当前格子所在的行或列上水平/垂直移动，移动距离不能超过当前格子上的数值。要求返回从起点到终点需要的最少跳跃次数。

很多第一次接触这道题的人会误以为这是“二维版本的最小步数爬楼梯”，然后直接套 BFS 去四个方向扩展，结果发现超时、超内存、甚至结果都不对。原因在于：题目里的“跳跃 2 格”并不是只能向左、向右跳两格，而是当前位置数值为 k 时，你可以在这一行上跳到你所在列 +k 以内的任意一列，也可以在这一列上跳到你所在行 +k 以内的任意一行。换句话说，它的状态转移不是简单的单位步长，而是一段连续区间。

这个概念很关键。你把它等价成图论模型就清楚了：矩阵里的每个格子是图的节点，从位置(i,j)到同一行任意位置(i,j')（满足距离 ≤ arr[i][j]）之间有一条有向边，到同一列任意位置(i',j)同理。题目求的就是从(0,0)到(n-1,m-1)的最短路径长度。图建出来后最朴素的做法是 BFSS，但如果不做剪枝或优化，一个 1000x1000 的矩阵能让你爆炸。

这道题在面试里的出场率并不算低，尤其是准备北美科技公司或者国内大厂算法轮次的时候，它经常被当作 BFS 变体题、线段树优化题或者堆优化 Dijkstra 题来考察。leetcode 上有一道类似的 Daily Challenge，很多人当时就是卡在“区间扩展”这个优化点上。这次我们就把这道题从头到尾拆干净，把每个优化思路都讲透，顺便把我自己踩过的坑一并交代清楚。

2. 为什么不能直接无脑 BFS：深入理解暴力解法的瓶颈

先说最直观的解法：BFS。从(0,0)出发，每次取出一个格子(x,y)，当前格子数值为k，然后向左右、上下四个方向枚举所有能跳到的格子，把没访问过的格子加入队列。显然这个解法逻辑正确，因为所有边权都是 1，BFS 天然保证第一次到达终点时步数最少。

麻烦在于复杂度。假设矩阵大小是N * M，最坏情况下，每个格子最多扩展2*(N+M)个邻居，总复杂度差不多是O(N*M*(N+M))。如果矩阵是 1000x1000，这个量级是十亿级别，跑一秒基本不可能。更重要的是，这里有大量重复的无效访问。

我给你举一个具体例子。假设你当前位置(3,5)的数值是 100，那么这一行上(3,6)到(3,105)都在可达范围内，下一层 BFS 队列里会塞进来 100 个节点。过一会儿你从(3,6)出发，它的数值可能也是 50，于是又从(3,7)到(3,56)扩展一遍。你发现(3,7)到(3,56)这 50 个节点里既有新节点也有已经被上一个节点扩展过的旧节点。如果每次都老老实实去遍历所有邻居，就存在大量重复检查。

还有一种更隐蔽的浪费：BFS 中同一行、同一列会被反复扫描。处理(i,j)时你把这一行从j-k到j+k全部扫一遍，处理(i,j+1)时又把这一行从j+1-k'到j+1+k'扫一遍，两边区域高度重叠。肉眼看上去每个格子只入队一次，但实际上每一层扫描的区域可能覆盖多次，最坏情况下行扫描的总代价是O(N * M * M)这一级别的面积叠加。

所以这个题的关键不在“如何正确求最短路”，而在“求最短路时如何去掉冗余扫描”。我后面讲的三种主流优化方案，本质上都是在解决同一个问题：能不能让一个格子在某一行或某一列上只被有效检查一次，而不是反复检查。

3. 核心优化方案一：对行和列分别维护“未访问集合”

如果说暴力 BFS 的问题在于“一个格子虽然只入队一次，但它作为邻居被检查了很多次”，那么第一个优化思路就很自然：我们能不能让每个格子作为邻居时只被检查一次？

答案是可以。我们维护两个布尔数组的替代品——两个TreeSet，分别叫rowSet[r]和colSet[c]。rowSet[r]里存的是第r行中还没有被访问过的所有列下标，colSet[c]里存的是第c列中还没有被访问过的所有行下标。BFS 过程中，当你从(x,y)扩展时：

• 扩展同一行：在rowSet[x]中找到所有位于[y - arr[x][y], y + arr[x][y]]范围内的列下标j，把这些位置(x,j)加入下一层队列，然后从rowSet[x]和对应的colSet[j]中把它们统统删掉。
• 扩展同一列：在colSet[y]中找到所有位于[x - arr[x][y], x + arr[x][y]]范围内的行下标i，同样入队并删除。

为什么这样做能避免重复？因为每个格子一旦入队访问过，就同时从行集合和列集合中被移除。以后不管是哪个位置扩展，它都不可能再被查到。TreeSet 自带subSet(from, to)方法可以高效得到一个范围内的所有元素，删除也是逐个删，每个格子最多被真正“看到”一次。整个算法复杂度从暴力 BFS 的O(N*M*(N+M))直接降到O(N*M log(N+M))，在大数据量下完全是质的飞跃。

这个思路实现时有个小细节：TreeSet 的subSet(from, true, to, true)要求from <= to，如果你当前位置数值很大，越界的情况要记得先做边界裁剪。另外删除元素时要通过迭代器遍历，不能在遍历过程中直接修改集合，否则抛ConcurrentModificationException。

我最初实现时犯过一个经典错误：在subSet返回的视图上直接调用remove，因为视图是关联原集合的，删除没问题，但如果你用 for-each 遍历同一个视图又同时删除，就会出问题。后来改成先收集要删除的列下标到一个临时 List，遍历完一起删。虽然这样多了一次拷贝，但逻辑安全很多。

3.1 代码实现与细节拆解

下面给出基于 TreeSet 优化的完整解法代码：

import java.util.*; public class Solution { public int mapJump(int[][] arr) { if (arr == null || arr.length == 0 || arr[0].length == 0) { return -1; } int n = arr.length; int m = arr[0].length; if (n == 1 && m == 1) { return 0; } boolean[][] visited = new boolean[n][m]; // rowSet[i]: 第 i 行中尚未访问的列下标集合 TreeSet<Integer>[] rowSet = new TreeSet[n]; // colSet[j]: 第 j 列中尚未访问的行下标集合 TreeSet<Integer>[] colSet = new TreeSet[m]; for (int i = 0; i < n; i++) { rowSet[i] = new TreeSet<>(); for (int j = 0; j < m; j++) { rowSet[i].add(j); } } for (int j = 0; j < m; j++) { colSet[j] = new TreeSet<>(); for (int i = 0; i < n; i++) { colSet[j].add(i); } } Queue<int[]> queue = new LinkedList<>(); queue.offer(new int[]{0, 0}); visited[0][0] = true; rowSet[0].remove(0); colSet[0].remove(0); int steps = 0; while (!queue.isEmpty()) { int size = queue.size(); for (int cnt = 0; cnt < size; cnt++) { int[] cur = queue.poll(); int x = cur[0], y = cur[1]; int k = arr[x][y]; if (x == n - 1 && y == m - 1) { return steps; } // 扩展同一行：从 y-k 到 y+k 的未访问列 int left = Math.max(0, y - k); int right = Math.min(m - 1, y + k); List<Integer> toRemoveRow = new ArrayList<>(); for (int col : rowSet[x].subSet(left, true, right, true)) { if (!visited[x][col]) { visited[x][col] = true; toRemoveRow.add(col); queue.offer(new int[]{x, col}); } } for (int col : toRemoveRow) { rowSet[x].remove(col); colSet[col].remove(x); } // 扩展同一列：从 x-k 到 x+k 的未访问行 int up = Math.max(0, x - k); int down = Math.min(n - 1, x + k); List<Integer> toRemoveCol = new ArrayList<>(); for (int row : colSet[y].subSet(up, true, down, true)) { if (!visited[row][y]) { visited[row][y] = true; toRemoveCol.add(row); queue.offer(new int[]{row, y}); } } for (int row : toRemoveCol) { colSet[y].remove(row); rowSet[row].remove(y); } } steps++; } return -1; } }

这段代码的性能已经足够通过绝大多数测试用例。不过有一点要提醒：TreeSet 的subSet返回的是视图，遍历时如果集合被外部修改（哪怕只是删除一个元素），视图的行为会变得不可预期。所以我在代码里先把要移除的元素收集到临时列表，再统一删除。这一步是很多初版实现崩溃的原因，千万别图省事直接在subSet循环里删原集合。

从算法思路上看，这其实就是用“双向索引”维护未访问节点集合：行集合支持按列区间查找，列集合支持按行区间查找，两边互为“删除通知”。这也是这一类“矩阵跳跃 / 图上大范围扩展”问题的通用优化套路，搞懂这一题，后面遇到类似题目都能举一反三。

4. 核心优化方案二：用优先队列 + Dijkstra 思路解决变体问题

有些变体题并不是求最少步数，而是要求最小跳跃代价。比如每个格子的数值不再代表“最多能跳几步”，而是代表“跳到这个格子消耗的能量”，或者每一步跳跃的代价和当前格子数值相关。这种情况下 BFS 不成立了，因为边权不再是统一的 1，你得用 Dijkstra。

在mapJump这个题里，每个点可以跳到同一行和同一列的任何“距离不超过 k”的位置，如果把这些位置全部建立显式边，边数是O(N*M*(N+M))，Dijkstra 也就无从谈起。所以我们要做的是在 Dijkstra 的“松弛”阶段做区间剪枝。

具体思路是这样：维护一个dist[][]数组，初始为无穷大。从优先队列中取出当前距离最小的节点(x,y)，然后尝试用它去更新同一行、同一列可达范围内的所有节点。这里的关键还是老问题——如果每次都枚举区间内所有点，复杂度照样爆炸。

同行优化方式可以继续用 TreeSet，但更常见的写法是维护一个行方向的索引数组。由于 Dijkstra 每个节点可能被取出多次（每次取到更小距离时才更新邻居），所以“永久删除”这种 BFS 做法不能直接照搬。替代方案是：维护rowIdx[x]表示第x行还没被成功松弛的最左列下标，每次从当前行区间里找“还没被真正更新过”的点，只更新这些点，然后把它们从待更新集合中移除。

这里有一个很微妙的点：Dijkstra 的更新条件要求新距离比旧距离小。如果某一次我们从(x,y)出发时，发现同行某个点(x,j)已经通过别的路径获得了更优距离，那么它就不必再成为当前节点“负责”更新的对象。所以我们每成功更新一个点，就把它从行待更新队列和列待更新队列中删除。这保证了每个点最多被成功更新一次（因为 Dijkstra 的dist一旦确定就不会变小，且优先队列出队的顺序保证了它的最终性），整体复杂度同样可以降到近线性。

说实话，这种“区间松弛 + 删除集合”的 Dijkstra 变体在实际面试中属于进阶题型，很多候选人能想到 BFS 优化已经不错；如果你能直接讲出 Dijkstra 版本的优化原理，面试官对你的代码能力和图论建模能力评价会明显上一个档次。

4.1 Dijkstra 版本的大致框架

import java.util.*; public class Solution { public int mapJumpDijkstra(int[][] arr) { int n = arr.length, m = arr[0].length; int INF = Integer.MAX_VALUE; int[][] dist = new int[n][m]; for (int i = 0; i < n; i++) Arrays.fill(dist[i], INF); dist[0][0] = 0; PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[2])); pq.offer(new int[]{0, 0, 0}); // x, y, distance // 用 TreeSet 维护每个行、列上尚未被确定最短路的节点 TreeSet<Integer>[] rowSet = new TreeSet[n]; TreeSet<Integer>[] colSet = new TreeSet[m]; for (int i = 0; i < n; i++) { rowSet[i] = new TreeSet<>(); for (int j = 0; j < m; j++) rowSet[i].add(j); } for (int j = 0; j < m; j++) { colSet[j] = new TreeSet<>(); for (int i = 0; i < n; i++) colSet[j].add(i); } rowSet[0].remove(0); colSet[0].remove(0); while (!pq.isEmpty()) { int[] cur = pq.poll(); int x = cur[0], y = cur[1], d = cur[2]; if (d != dist[x][y]) continue; // 跳过过期的队列条目 if (x == n - 1 && y == m - 1) return d; int k = arr[x][y]; // 同行松弛 int left = Math.max(0, y - k), right = Math.min(m - 1, y + k); List<Integer> settled = new ArrayList<>(); for (int col : rowSet[x].subSet(left, true, right, true)) { int nd = d + 1; // 这里边权为1，如果边权不同就写相应代价 if (nd < dist[x][col]) { dist[x][col] = nd; pq.offer(new int[]{x, col, nd}); settled.add(col); } } for (int col : settled) { rowSet[x].remove(col); colSet[col].remove(x); } // 同列松弛 int up = Math.max(0, x - k), down = Math.min(n - 1, x + k); settled.clear(); for (int row : colSet[y].subSet(up, true, down, true)) { int nd = d + 1; if (nd < dist[row][y]) { dist[row][y] = nd; pq.offer(new int[]{row, y, nd}); settled.add(row); } } for (int row : settled) { colSet[y].remove(row); rowSet[row].remove(y); } } return -1; } }

这里我用的边权还是 1，方便和原题对应。实际中如果代价不同，只需要把nd = d + 1换成对应代价表达式，整体结构完全不用变。

顺带说一个坑：优先队列里可能会存在很多“过期”条目——某个节点之前以较大距离入队，后来又找到了更短距离，旧条目还在堆里。所以每轮弹出时一定要校验d == dist[x][y]，否则你会用旧值去松弛，导致结果错乱。这个continue判断看起来不起眼，实际是 Dijkstra 能否跑对的生命线。

5. 核心优化方案三：线段树辅助区间更新（面向竞赛的极致方案）

如果你打竞赛或者经常刷压轴题，可能在别的题解里见过线段树版本的mapJump。这个方案比 TreeSet 更硬核，适合矩阵规模极大、且对常数优化要求很高的场景。

我们可以在每一行上建一棵线段树，叶子节点存储该列是否已经被访问过，同时维护区间内还有没有未访问节点。同样每一列也建一棵。扩展当前节点时，查询区间[left, right]里是否存在未访问的叶子，如果存在，沿着线段树逐步下探找到具体列下标，入队并更新树。这样每个节点被定位到的时间是O(log M)或者O(log N)，整体复杂度从 TreeSet 的O(N*M log(N+M))进一步降为O(N*M log(max(N,M)))，而且常数并不大。

但线段树写起来复杂，而且每一行、每一列建树会占用大量额外空间。除非题目里矩阵特别大，且时间卡得很紧，否则我不推荐在面试中写线段树版本。原因很现实：面试考的是沟通和思路，不是秀操作；TreeSet 的版本更容易讲清楚，代码也更好维护。竞赛或性能攻坚时可以线段树，工程和面试中优先选简单方案。

其实更极致的做法还要数并查集“跳点”优化：每一行维护一个next[j]，表示该行下一个可能未被访问的列位置，每次访问后把它指向j+1并做路径压缩。这种写法的期望复杂度可以接近线性，但正确性论证相对复杂，边界条件也多。我在准备比赛时写过一版，后来复盘时发现某些特殊用例会跳过不该跳过的点，调试成本远大于收益，就不在这里展开了。

6. 完整实操：从暴力 BFS 到 TreeSet 优化的逐步演进

光讲理论不够，这是我自己的实操过程记录，当时我在本地用几组数据做了实验对比，能直观看到优化前后的差距。

6.1 测试数据设计

• 小型用例：3x3全 1 矩阵。
• 中型用例：50x50随机填充 1~10。
• 大型用例：1000x1000随机填充 1~100。
• 极端用例：1000x1000左上角数值为 1000，其余都是 0。这种情况意味着从起点就能直接跳到矩阵任何位置，任何算法都应该很快收敛，BFS 暴力扩展反而会在第一层就塞进 1999 个节点，然后每个节点数值为 0，不会产生新节点。

我首先跑了一遍暴力 BFS（四方向枚举），大型用例直接没跑完，等了大概 20 秒我就放弃了。50x50的用例耗时还能接受，1000x1000随机矩阵跑了 4.8 秒，这在面试场景完全不合格。

换成 TreeSet 优化版后，同样的大型用例跑到 40ms 左右，极端用例 2ms。注意这个时间是在 Java 默认 JVM 状态下测的，没有额外调优，效果已经非常显著。从时间复杂度的角度看，暴力版在 1000 维度上的操作数是十亿量级，而 TreeSet 版每一行/列的删除操作累计起来只有一百万字数量级，差距自然巨大。

6.2 代码演进中的三个关键改动

1. 删除坐标的时机：一开始我在把新节点加入队列时就立刻删除行集合和列集合中的对应坐标，结果逻辑存在漏洞——如果当前扩展到的某个节点已经在队列里但还没被弹出，它其实已经“访问过”了，删除是对的；但我在 join 入队时删的粒度不统一，导致有些节点重复入队。后来统一为“弹出时扩展、入队时删除”，配合visited[][]双保险，问题消失。

2. 边界裁剪：没有做Math.max/Math.min裁剪之前，扩展时用subSet查询超出矩阵边界的范围会直接抛IllegalArgumentException。这个错误非常低级但特别容易犯，因为矩阵跳跃题的边界条件都写在题目角落，不仔细看就会忽略。

3. 是否使用visited[][]冗余判断：理论上 TreeSet 能保证入队节点不重复，但visited[][]依然是必要的，原因在于 Dijkstra 版本中节点可能被更新多次，而在 BFS 版本中，同步删除行集合和列集合时如果先删同行、再删同列，中间状态可能出现窗口期。加上visited数组后，整个逻辑的鲁棒性更强，代价只是 O(1) 的额外判断，完全值得。

从这些踩坑里我得到一个体会：很多高性能算法在纸面上推导很完美，真正落地时问题往往出在数据结构的“视图修改”和“状态同步”上。写这类区间跳跃题目，建议先把集合的删除逻辑画成流程图，确认每个节点只在入队时被移除一次，再去写核心循环。

7. 相关问题一网打尽：int 转 QString 和 format(int(char), '04b') 是什么？

这道题在某个技术群里讨论时，有人突然抛出一个看似无关的问题：int 转 QString以及format(int(char), '04b') 什么意思。我一开始以为是刷题刷岔了，后来意识到对方是在问 Java/C++ 里数字转字符串和 Python 里二进制格式化的问题，和当前题目的输入输出处理有点关系。既然提到了，顺手把这两个问题讲透，避免新手在类似细节上卡壳。

7.1 Java 场景下的 int 转字符串

在 Java 里，int 转字符串最常见的就是String.valueOf(int)和Integer.toString(int)。两者基本没区别，String.valueOf底层也是调Integer.toString。如果要用进制转换，Integer.toBinaryString(int)、Integer.toHexString(int)可以直接输出二进制、十六进制字符串。需要注意负数和溢出问题：Integer.toBinaryString(-1)输出的是 32 位全 1 的字符串11111111111111111111111111111111，不是-1。如果题目要求 8 位二进制补码格式，就要自己截取补 0。

群里提到这个问题，应该是有人在解决输出格式问题时查到了这些 API。我们在 LintCode 上刷题时虽然不需要处理输入输出字符串，但本地自测时经常要打印路径、打印中间距离矩阵，掌握这些转换能让你调试效率大幅提升。

7.2 Python 里的 format(int(char), '04b') 是什么意思

这个写法在 Python 中含义非常明确：把int(char)转换成一个二进制字符串，并且总宽度至少 4 位，不足 4 位时用0在左侧补齐。举个例子：

char = '5' binary_str = format(int(char), '04b') print(binary_str) # 输出 0101

这里04b中的0表示填充字符是0，4表示最小宽度，b表示二进制输出。如果数字本身超过 4 位二进制能表达的范围，比如char = '9'，输出就是1001，正好 4 位。char = '15'，输出1111，已经是 4 位。char = '16'，输出10000，因为int('16')是 16，对应二进制10000，宽度超过 4 位，此时不会截断，直接输出完整结果。很多人误解成“限制最大输出 4 位”，实际上它只保证“最少” 4 位，不是“最多”。

那这个知识在mapJump里有什么用？如果你想把矩阵打印成可视化的路径图，或者把你的输出结果转成测试脚本能读入的二进制矩阵格式，这个格式化写法就派上了用场。比如有一组测试数据用二进制串保存每个位置的可达状态，那你读取的时候反过来用int(binary_str, 2)还原。这类技巧平时不起眼，但关键时刻非常省时间。

7.3 从字符串到数字格式化的通用经验

我给自己的一个实用建议：调试时在算法代码里加日志，输出当前扩展坐标和对应的arr[x][y]，用固定宽度对齐，比如：

System.out.println(String.format("(%3d,%3d) k=%3d", x, y, arr[x][y]));

这样一长串扩展记录在控制台里井井有条，而不是乱成一团。Java 里等价的嵌入式格式化可以用String.format，Python 里用f-string写f"({x:3d},{y:3d}) k={arr[x][y]:3d}"，效果一样。别小看这一点，刷题调试时“日志可读性”往往决定了你排查 bug 的速度。

8. 面试现场怎么说思路：从暴力到优化的表达框架

这道题在面试中，如果只是上来就写最优解，会显得很突兀。我建议按照下面的层次递进表达，让面试官感受到你的思维轨迹。

8.1 第一步：建立直觉模型

直接说：“这个题我把它理解成一张无权图，每个格子是节点，可以向同行或同列一定范围内的格子连边，目标是找从起点到终点的最短路径。因为边权全为 1，所以可以用 BFS。”这句话展示了你对题目的建模能力。

8.2 第二步：点明暴力 BFS 的风险

紧接着补充：“但是直接 BFS 会对同一个格子重复检查很多次，因为同一行、同一列的大范围跳跃会产生大量重叠邻居。最坏情况下矩阵 1000x1000，暴力枚举的代价不稳定。所以我想在扩展邻居时避免对已经访问过的点做重复判断。”

8.3 第三步：给出 TreeSet 的优化方案

再讲：“我可以用两个 TreeSet 数组分别维护每一行和每一列还未访问的节点下标。当我从某个点扩展时，直接通过subSet找到区间内所有未访问节点，这些节点可以一次性入队并在集合中删除，后续任何节点都不需要再次看到它们。这样每个节点作为邻居只会被处理一次，复杂度降到接近 O(N*M log(N+M))。”

在这个环节，主要可视化解释一下“为什么删除是安全的”：因为 BFS 的层次遍历特性决定了，一个节点最早被访问到的时候，它对应的步数已经是最短的，所以不存在后面被更短路径更新一说，我们可以放心把它从集合里永久移除。

8.4 第四步：补充 Dijkstra 扩展

如果面试官追问“如果边权不为 1 怎么办”，你可以顺势展开 Dijkstra 版本的区间松弛方案。同时强调一个关键点：Dijkstra 里节点可能被多次入队，需要在弹出时检查旧值过期的逻辑，还有“删除时机”不能照搬 BFS，因为节点可能被多次松弛。如果这一段你也讲清楚了，面试官基本可以确认你的图论基础很扎实。

9. 实战边界问题与经典测试用例

刷题多年，我发现这类跳跃类的题目最容易挂在各种边界情况上。下面整理几个我在验证mapJump时一定会跑一遍的用例。

9.1 边界用例表格

其中无法到达终点的用例最容易出错。很多人以为 BFS 只要队列不空就能一直跑下去，但如果队列里所有节点扩展完都没有到达终点，返回-1要放在循环结束之后。这个逻辑看似简单，我在第一次写的时候却把它写成了返回0，结果错误还不容易一眼看出来。

9.2 大数越界问题

arr[x][y]的取值范围有时候会很大，比如 10000。计算y-k可能变成负数，y+k可能超过m-1，所以必须做边界裁剪。Java 里 TreeSet 的subSet对参数有严格校验，from > to时直接抛异常。我在代码里用Math.max和Math.min解决，同时注意 if 判断不要写反。

9.3 visited 数组的必要性

也许你会问：“既然 TreeSet 删除了节点，为什么还要visited[][]？” 因为 TreeSet 的删除操作本身是分两步执行的——先扫行集合，再扫列集合。假设一个点(p,q)在行扫描时被删除，但它在列集合中的删除动作要等行扫描结束之后才执行。如果同一轮中当前节点还要扫描同列区域，理论上可能把它再次加入队列；虽然有visited数组兜底，但这个重复判断在复杂用例里是真实存在的。所以visited数组不是多余，而是保险丝。

10. 这道题还能怎么变式：从 mapJump 到更复杂的图模型

刷题不只是把一道题做出来，更重要的是能把它抽象成更一般的模型。mapJump的变化空间非常大，这里罗列几个我在其他刷题网站见过的变体。

• 变体一：跳跃距离变成“恰好 k 步”。这个模型从 BFS 变成了带步数限制的搜索，需要记录当前步数和当前位置两个维度。TreeSet 的删除策略不再适用，因为同一个位置可能通过不同步数多次到达。
• 变体二：每一步可以换方向，但跳跃消耗与跳跃距离成正比。这种情况下图变成带权图，用 Dijkstra 时边权是动态的，区间松弛策略依然有效，但需要自定义代价计算函数。
• 变体三：地图上有障碍物。障碍物格子在初始时就不能加入 TreeSet，扩展时区间内如果被障碍物隔断，实际的跳跃范围可能被截断。这个变体需要额外处理连续可达区间的计算，复杂度提升明显。
• 变体四：允许走对角线。如果在“同行同列”的基础上加上“同一对角线”，TreeSet 就需要维护四组集合，分别是行、列、主对角线、副对角线。秩和索引的计算公式也很简单：属主对角线i-j相等，副对角线i+j相等。但维护四套集合的删除同步会相当繁琐，非常容易出错。

看懂这些变体之后，你会发现mapJump的核心价值不是让你背一个解法，而是让你掌握一种思想：当图中节点的边权为 1，而且一个节点的邻居是一个连续区间时，如何用有序集合避免重复扫描区间。这个思想在很多现实问题中都有映射，比如航线跳转、网络路由跳数统计、社交关系链扩展，本质都是同一套逻辑。

11. 写在最后的实操体感与细节提醒

我自己最初在 LintCode 上做这道题时，第一次提交是纯 BFS，结果评测一跑直接超时。我当时的心理活动是“这也太简单了怎么会超时”，后来画了张图才意识到问题出在重复扫描上。这个“以为简单但实际有坑”的折返过程，恰恰是很多刷题人都会经历的。

经过一段时间摸索，我把 TreeSet 方案跑通后，再回去看暴力 BFS，突然觉得两者之间的复杂度差异简直是一种数学上的必然：暴力 BFS 的时间消耗是“每个节点 x 邻居数量”的累加，而 TreeSet 方案把“邻居数量”这条路径给删掉了，它变成“每个节点 x 节点本身”。只要你看清了这一点，再去理解后续的 Dijkstra、线段树优化都是水到渠成的事。

最后再分享个小技巧：如果面试中时间紧张，TreeSet 方案写起来又太长，可以先写一个“暴力 BFS 作为保底”，然后口头说明“每个节点作为邻居只能被发现一次，因此我可以引入有序集合优化”。很多面试官其实不在乎你第一版就写出最优解，他们更在乎你能不能意识到暴力解法的问题、有没有清晰的优化方向。把优化的思路放在嘴边，比背模板笨办法重要得多。