T717314这道题一摆出来JOJO粉丝多半会先会心一笑——《滚石》这篇外传短篇把“命运”两个字玩到了极致米斯达在墓地里遇见那块石头时还天真地以为可以跟命运掰掰手腕。出题人明显也懂这个梗把替身能力原封不动搬进了题面地图上有一颗滚石它不能一格一格挪选定方向后就一路滚到撞墙才停。第一次看这题的时候我心里就在想这文案很JOJO可核心不就是经典滑动BFS吗读懂题面后解法其实比想象中清晰但真要把边界、预处理、判重全写对还是会踩不少坑。这篇题解会从“替身能力如何翻译成算法模型”讲起再给出朴素BFS和O(HW)预处理两版实现最后把调试中容易翻车的点整理成速查清单。无论是想练BFS的新手还是想彻底搞懂“滚动小球”这类题通用套路的老手这篇应该都能给你些参考。1. 先把题目读懂从替身能力到算法语言1.1 JOJO里的滚石到底能做什么《滚石》是JOJO第五部连载结束后推出的短篇讲的是米斯达偶然得到一块奇怪的石头这块石头会指向“注定死亡的人”并且一旦锁定目标就会像宿命一样滚向对方。你没法让它转向没法让它停下只能眼睁睁看着它沿着轨迹一路碾压过去。这个设定其实非常像一类算法题里常见的“滑动”模型物体不能逐格移动一旦开始运动就必须沿着一个方向走到头直到被障碍物或边界挡住才会停下。T717314这道题把这两个元素结合得很巧妙——题目名叫“滚石”题面的运动规则也确实是“滚”不是“走”。如果你没看过JOJO也没关系做题时只需要记住三条滚石每次只能选择一个方向上、下、左、右。选定方向后它会一直滚动直到撞到障碍物或地图边界。它只会停在障碍物前一格或边界格不能在途中随便停下来。换句话说地图上真正能停的位置不是所有空地而是那些“沿某一方向滚过去会被墙或者边界挡住”的位置。这个认知是整个解题思路的第一块基石。1.2 完整题面与数据范围T717314原题的大致形式如下我按OJ常见风格整理题目背景一块被替身能力激活的滚石出现在地图上它会自动滚向被命运锁定的人。给定一个H行W列的网格地图由空地.和障碍物#组成。滚石从起点S出发每次可以选择一个方向并一直滚动直到撞到障碍物或地图边界才停下。问滚石最少需要滚动多少次才能正好停在终点T上如果永远无法到达输出-1。输入第一行包含两个整数H和W。接下来H行每行是一个长度为W的字符串表示地图。地图中保证恰好有一个S和一个T二者都位于空地上。数据范围1 ≤ H, W ≤ 1000且H×W≤1000000。这里我补充一个自测样例方便理解题意5 6 S..... .####. ...... .####. .....T答案是2。走法很简单先从S向下滚这一列没有障碍物所以滚到地图最下边停在(4,0)再从(4,0)向右滚整行都是空地正好滚到T所在位置(4,5)停下。两步完成。这个样例也顺便暴露了一个关键信息终点T必须是一个“能停下来的位置”才算到达。如果T在半路上比如前后都没有障碍物或边界阻挡那滚石只会从它身上碾过去但不会停在上面这种情况依然算不可达。1.3 从样例看出“停止点”才是状态如果你第一次做这类题很容易下意识把它当成普通四连通BFS从S出发每次向四个方向走一格。但滚石的规则完全不是这样它一次移动可能跨越好几个格子中间经过的所有格子都不构成有效状态。这就引出本题最重要的抽象方式把“停下来的格子”当作状态把“从当前停靠点开始朝某个方向滚到另一个停靠点”当作一条边。为什么这个抽象是合理的因为滚石在两次停止之间没有任何决策空间方向一旦定了中途会经过哪些格子、最终停在哪个格子都是完全确定的。你不需要关心它经过了哪里只需要关心它从哪里停下来、下一次又能从哪里停下来。到这里题面已经成功转译成图论问题。接下来就是怎么高效地求解最短滚动次数。2. 思路推导为什么是无权最短路以及复杂度瓶颈2.1 把每个停靠点看成图上的一个点先看一个小问题如果已经知道每个停靠点可以向四个方向滚动到哪些停靠点那么这题还剩什么难度其实就剩一个经典的最短路模型。每次滚动代价是1所有边权都相等要求从S到T的最少滚动次数这正好是无权图上的最短路径问题用BFS就能在线性时间内解决。这里我提一下为什么不用DFS也不用Dijkstra。DFS在无权图上求最短路是个大坑。它天然不保证先找到的路径最短除非你把所有可能路径全搜一遍然后取最小值。可“所有可能路径”在这种图上很容易指数爆炸因为你可能反复绕回之前经过的停靠点。加上记忆化、剪枝复杂度依然不如BFS直观写出来还容易出错。Dijkstra倒是能求最短路但它的优先队列会带来O(E log V)的复杂度。既然所有边权都是1BFS只要O(VE)完全没必要引入log的代价。越简单的东西越不容易出bug这是竞赛老油条们的共识。所以你只要记住状态越少、转移越清晰的问题越适合BFS。T717314恰好就是这种题。2.2 朴素模拟的写法与复杂度陷阱没有接触过预处理优化之前最自然的写法是每次从当前停靠点出发枚举四个方向再用一个while循环沿着方向一直走直到越界或撞墙停下来。伪代码大概是while (真) { nx dx[i]; ny dy[i]; if (nx 0 || nx n || ny 0 || ny m || mp[nx][ny] #) break; } // 此时 (nx - dx[i], ny - dy[i]) 就是本次滚动停下的位置这个写法在数据范围比较小的时候完全没问题比如H、W都不超过50直接暴力扫就行。可一旦数据拉到1000×1000也就是上限100万个格子朴素模拟的复杂度就有点吓人了。想一想每个停靠点最多扩展四个方向每个方向最坏会沿着整行或整列滚到底也就是一次转移最多扫O(max(H,W))个格子。总共的复杂度大概是O(HW·(HW))。当HW1000时这个数大约是1e6×2000也就是20亿次操作。20亿次循环在现代CPU上也很难在1秒内跑完遇到严格的评测机直接超时。所以朴素BFS只能算“思路正确”不能算“能AC的最终解法”。如果你只想交一版过小数据的代码可以这么写但在T717314这种题目设定下我强烈建议一步到位把预处理优化也掌握。2.3 预处理四个方向的落点把转移从O(max(H,W))降为O(1)既然瓶颈在于“每次滚动都要重新扫一遍地图”那解决办法就很明确了提前算出每个位置向四个方向滚动后会停在哪里让BFS转移时直接查表而不是现场模拟。问题变成怎样快速计算所有位置的“四向落点”这里有个特别经典的技巧把地图外部也想象成无限延伸的墙。这样一来向左滚最终一定停在当前行“左边最近的墙”的右侧一格向右滚停在“右边最近的墙”的左侧一格向上滚、向下滚同理。拿“向左滚”举例。对于第i行我从左往右遍历这一行同时维护一个变量lastWall表示“当前位置左侧最近一次遇到的墙的列号”。初始时lastWall-1代表地图左边界外有一堵虚拟墙。如果当前格子是空地那么left[i][j] lastWall 1意思是向左滚会停在最近墙的右边一格。如果当前格子是墙就更新lastWall j。向右滚就反过来从右往左扫维护右侧最近墙的位置。向上滚、向下滚也完全一样只是从行遍历换成了列遍历。这样扫一遍只需要O(HW)的时间就能得到四个方向落点数组。之后BFS里每个状态扩展时直接读四个数组转移变成O(1)。整个算法复杂度从20亿次级别下降到百万级别质的飞跃。3. 代码实现朴素版和预处理优化版双保险3.1 通用框架状态表示与dist数组写代码之前先统一一下状态表示。我习惯用一维编号代替pairint,int做队列存储。对于坐标(x,y)定义id x * m y恢复坐标时用x id / my id % m。这样做的好处是dist数组可以开成一维的BFS判重和赋值都更直观。int dirx[4] {-1, 1, 0, 0}; int diry[4] {0, 0, -1, 1}; vectorint dist(N, -1); // N n * m queueint q;dist初始化为-1既表示“未访问”也方便最后输出。把起点dist设为0后入队然后正常跑BFS。3.2 朴素BFS版本先给出朴素版完整代码。这个版本可以用于小数据范围验证思路也可以拿来跟优化版对拍。#include bits/stdc.h using namespace std; const int MAXN 1005; string mp[MAXN]; int n, m; int sx, sy, tx, ty; int dirx[4] {-1, 1, 0, 0}; int diry[4] {0, 0, -1, 1}; int dist[MAXN * MAXN]; int bfs_naive() { if (sx tx sy ty) return 0; memset(dist, -1, sizeof(dist)); int S sx * m sy; dist[S] 0; queueint q; q.push(S); while (!q.empty()) { int id q.front(); q.pop(); int x id / m; int y id % m; for (int k 0; k 4; k) { int nx x dirx[k]; int ny y diry[k]; // 沿 k 方向滚动直到越界或撞墙 while (nx 0 nx n ny 0 ny m mp[nx][ny] ! #) { nx dirx[k]; ny diry[k]; } // 回退一步得到真正停下的位置 nx - dirx[k]; ny - diry[k]; int nid nx * m ny; if (dist[nid] -1) { dist[nid] dist[id] 1; if (nx tx ny ty) return dist[nid]; q.push(nid); } } } return -1; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n m; for (int i 0; i n; i) { cin mp[i]; for (int j 0; j m; j) { if (mp[i][j] S) { sx i; sy j; } else if (mp[i][j] T) { tx i; ty j; } } } cout bfs_naive() \n; return 0; }这段代码在H、W不太大的时候能直接跑出正确结果我在上面的样例里实测输出是2。但为什么说它只适合小范围因为while循环在最坏情况下会扫完一整行或一整列。假如数据范围变成1000×1000而且地图里几乎没有墙那每个格子向左右滚都会扫1000个格子向上下滚也会扫1000个格子。BFS本身要访问的停靠点数量多达百万级乘上每次2000次扫描运行时间可想而知。所以在正式提交优化版前建议先用这个版本过一遍样例确认建模思路正确。3.3 预处理优化版核心代码接下来是重头戏先把所有位置的四周落点算出来再跑BFS。我定义四个二维数组up[x][y]、down[x][y]、left[x][y]、right[x][y]分别表示从(x,y)出发向四个方向滚动后停下的坐标。由于行列固定up/down记录停下的行号left/right记录停下的列号。#include bits/stdc.h using namespace std; const int MAXN 1005; string mp[MAXN]; int n, m; int sx, sy, tx, ty; int up[MAXN][MAXN], down[MAXN][MAXN]; int lft[MAXN][MAXN], rgt[MAXN][MAXN]; int dist[MAXN * MAXN]; void preprocess() { // 左边从左往右扫lastWall 表示左侧最近墙的列号 for (int i 0; i n; i) { int lastWall -1; // 地图左边界外视为墙 for (int j 0; j m; j) { if (mp[i][j] #) { lastWall j; } else { lft[i][j] lastWall 1; } } } // 右边从右往左扫 for (int i 0; i n; i) { int lastWall m; // 地图右边界外视为墙 for (int j m - 1; j 0; j--) { if (mp[i][j] #) { lastWall j; } else { rgt[i][j] lastWall - 1; } } } // 上边从上往下扫 for (int j 0; j m; j) { int lastWall -1; // 地图上边界外视为墙 for (int i 0; i n; i) { if (mp[i][j] #) { lastWall i; } else { up[i][j] lastWall 1; } } } // 下边从下往上扫 for (int j 0; j m; j) { int lastWall n; // 地图下边界外视为墙 for (int i n - 1; i 0; i--) { if (mp[i][j] #) { lastWall i; } else { down[i][j] lastWall - 1; } } } } int bfs() { if (sx tx sy ty) return 0; memset(dist, -1, sizeof(dist)); int S sx * m sy; dist[S] 0; queueint q; q.push(S); while (!q.empty()) { int id q.front(); q.pop(); int x id / m; int y id % m; int d dist[id] 1; // 四个方向直接查表不需要 while 循环 int nx, ny, nid; nx up[x][y]; ny y; nid nx * m ny; if (dist[nid] -1) { dist[nid] d; if (nx tx ny ty) return d; q.push(nid); } nx down[x][y]; ny y; nid nx * m ny; if (dist[nid] -1) { dist[nid] d; if (nx tx ny ty) return d; q.push(nid); } nx x; ny lft[x][y]; nid nx * m ny; if (dist[nid] -1) { dist[nid] d; if (nx tx ny ty) return d; q.push(nid); } nx x; ny rgt[x][y]; nid nx * m ny; if (dist[nid] -1) { dist[nid] d; if (nx tx ny ty) return d; q.push(nid); } } return -1; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n m; for (int i 0; i n; i) { cin mp[i]; for (int j 0; j m; j) { if (mp[i][j] S) { sx i; sy j; } else if (mp[i][j] T) { tx i; ty j; } } } preprocess(); cout bfs() \n; return 0; }这段代码里preprocess()是核心。你只需要理解一个地方的逻辑虚拟墙的初始值。向左滚时把左边界外当成墙初始lastWall-1所以第一块空地靠左滚会停在0向右滚时把右边界外当成墙初始lastWallm所以最右侧空地靠右滚会停在m-1。上下同理。这样边界情况完全不用单独特判。BFS部分从原来的“模拟滚动”变成“查表四连”代码虽然看起来长了点但每次转移都是O(1)即使数据范围拉满也跑得动。3.4 两版复杂度和适用场景对比版本预处理耗时BFS转移耗时总复杂度适合的数据范围朴素BFS无O(max(H,W)) / 次O(HW(HW))H,W ≤ 100左右预处理优化O(HW)O(1) / 次O(HW)H,W ≤ 1000甚至更大我的建议是比赛里遇到这类题直接写优化版。有人说优化版代码长怕写错——但实际上预处理的代码模式非常固定背下来以后就是机械操作。相比之下朴素版在评测机上超时之后再临时改优化版心态反而容易崩。4. 实战踩坑这些问题排查完基本就AC了4.1 容易翻车的五个细节第一个细节是起点和终点重合。地图里同时存在S和T正常情况下S不会等于T但万一出题人不按套路出牌呢如果S就是T答案应该是0而不是跑一遍BFS最后返回-1。竞赛里这种边界case虽然概率低但被坑一次就够难受了。第二个细节是终点不一定能停。滚石只有在撞墙或抵到边界时才会停。如果T所在的格子周围四个方向都没有墙或边界挡着那么T永远不可能成为一个停靠点。换句话说T虽然在地图上是空地但只要它不满足“某个方向存在阻挡”它就不会进入任何一次滚动的落点集合。这种情况直接输出-1即可不需要特殊标记因为BFS根本不会走到T。第三个细节是墙格子不能入队。在预处理数组里墙格子的up/down/lft/rgt可能是无意义的值比如-1也可能是上一轮扫描的残留值。如果你的BFS不小心从墙格子扩展轻则答案错误重则数组越界。所以我在代码里特意只在空地格子上触发BFS扩展墙格子天然不会成为队列里的元素。这个保证来自一个事实滚石的落点一定不是墙。第四个细节是while循环倒退一格。朴素版里最容易写错的就是滚动结束后忘了回退。如果你用while(nx0...) nx dirx[k]这种方式滚动循环退出时(nx,ny)已经越界或者踩到墙了必须往回退一格才是停靠点。很多新手第一次写都会漏这一步结果答案总是差一点。第五个细节是起点周围的墙可能导致0步到达。设S和T在同一个连通块里但S周围四面都堵死那S本身就是一个“死点”BFS从S扩展不出去最终返回-1。这也是符合题意的因为滚石第一步就动不了。4.2 常见问题速查表我把实际调试中可能遇到的典型问题整理成一张表方便你在卡题时快速定位。现象可能原因解决办法样例过不了朴素版while循环忘了回退一格滚动停止后把坐标回退到合法的停靠点输出答案偏大BFS里把经过的格子当成了状态只把滚动停止点作为状态入队输出-1但感觉有解终点不是停靠点或者起点四面被堵检查T是否满足“某方向有墙或边界阻挡”大数据超时用了朴素模拟每次转移扫整行使用预处理四向落点转移O(1)预处理的left和right反了左右扫描方向写反从左往右算left从右往左算right数组越界直接使用预处理数组里的-1BFS只处理空地格子预处理时给墙格子也赋合法值或后续判断4.3 我调试这个题时的经验我自己调试这类题时会额外打印每个停靠点的坐标和步数。比如在BFS里加一个临时输出cerr stop at ( nx , ny ), dist d \n;先把小样例的路径打出来人工走一遍确认逻辑对得上。对于1000×1000的大数据没法打印全量就用小数据对拍拿朴素BFS和预处理优化版各跑一遍随机生成地图比对答案。这种方法在竞赛里特别实用两个逻辑不同但结果应该相同的程序互相验证能迅速暴露方向、边界、状态表示上的各种问题。以后遇到“推箱子”“冰壶”“滚球”这类题也建议沿用这个套路先找“停下来”的状态再把滑动压缩成边最后考虑是否需要预处理转移。把这一套流程练成肌肉记忆T717314这样的题就能变成稳定的送分题了。