UVa 11705 Grasshopper

题目描述我们来到游乐场看到一个名为“蚱蜢迷宫”的蹦床阵列。每个蹦床上标有一个非负整数zzz表示从该蹦床起跳后必须在同一行或同一列上恰好跳过zzz个蹦床到达另一个蹦床即距离为zzz。迷宫的出口位于西北角(0,0)(0, 0)(0,0)位置用星号 * 标记。我们需要为每个蹦床标记出最优的跳跃方向使得从该蹦床出发按照标记的方向跳跃能够以最短的路径到达出口。路径的比较规则如下优先选择跳跃次数最少的路径若次数相同选择第一步能够到达最北行号最小的路径若仍然相同选择第一步能够到达最西列号最小的路径。输出一个字符矩阵每个位置可以是N,S,E,W表示从该位置向该方向跳跃是最优的X表示该位置无法到达出口*表示出口位置本身。输入格式包含多个测试用例。每个用例第一行是两个整数RRR和CCC1≤R,C≤501 \leq R, C \leq 501≤R,C≤50表示矩阵的行数和列数。接下来RRR行每行CCC个非负整数表示每个蹦床上的数值。以0 00\ 000结束输入。输出格式对于每个测试用例输出一个R×CR \times CR×C的字符矩阵每个字符代表该位置的最优跳跃方向。每个用例后跟一个空行。题目分析这是一个典型的最短路径问题但移动规则比较特殊从位置(i,j)(i, j)(i,j)出发如果该位置的值为zzz则可以跳到同一行(i,j−z)(i, j - z)(i,j−z)或(i,jz)(i, j z)(i,jz)同一列(i−z,j)(i - z, j)(i−z,j)或(iz,j)(i z, j)(iz,j)前提是目标位置在矩阵范围内。如果从每个位置正向BFS\texttt{BFS}BFS到出口时间复杂度较高。更优的做法是从出口反向BFS\texttt{BFS}BFS。反向BFS\texttt{BFS}BFS的好处是当我们第一次访问到一个位置时就找到了从该位置到出口的最短距离。然而反向搜索时我们需要考虑的问题变为哪些位置可以跳到当前点假设当前点为(r,c)(r, c)(r,c)值为vvv的点(nr,nc)(nr, nc)(nr,nc)能跳到(r,c)(r, c)(r,c)的条件是nrrnr rnrr且∣nc−c∣v|nc - c| v∣nc−c∣v同一行或者nccnc cncc且∣nr−r∣v|nr - r| v∣nr−r∣v同一列也就是说我们需要遍历同一行或同一列的所有点检查它们是否能一步跳到当前点。解题思路第一步反向BFS\texttt{BFS}BFS求最短距离我们从出口(0,0)(0, 0)(0,0)开始进行BFS\texttt{BFS}BFS使用队列qqq。对于队列中取出的每个点(r,c)(r, c)(r,c)我们检查所有可能跳到该点的位置同一列上对于每个行nrnrnr0≤nrR0 \leq nr R0≤nrRnr≠rnr \neq rnrr如果grid[nr][c]∣nr−r∣grid[nr][c] |nr - r|grid[nr][c]∣nr−r∣则说明(nr,c)(nr, c)(nr,c)可以一步跳到(r,c)(r, c)(r,c)。同一行上对于每个列ncncnc0≤ncC0 \leq nc C0≤ncCnc≠cnc \neq cncc如果grid[r][nc]∣nc−c∣grid[r][nc] |nc - c|grid[r][nc]∣nc−c∣则说明(r,nc)(r, nc)(r,nc)可以一步跳到(r,c)(r, c)(r,c)。将这些满足条件且尚未访问过的点加入队列并记录它们到出口的距离即当前点距离111。这样BFS\texttt{BFS}BFS结束后我们就得到了每个位置到出口的最短距离dist[i][j]dist[i][j]dist[i][j]。如果某个位置的distdistdist仍为−1-1−1则表示它无法到达出口。第二步根据规则确定方向对于每个可以到达出口的位置(i,j)(i, j)(i,j)除了出口本身我们需要确定最优的跳跃方向。我们有四个候选方向分别对应跳到北(i−z,j)(i - z, j)(i−z,j)南(iz,j)(i z, j)(iz,j)西(i,j−z)(i, j - z)(i,j−z)东(i,jz)(i, j z)(i,jz)其中zgrid[i][j]z grid[i][j]zgrid[i][j]。由于我们已经知道每个位置的最短距离distdistdist那么从(i,j)(i, j)(i,j)出发最优的下一步应该满足目标位置可达在矩阵范围内dist[目标]dist[i][j]−1dist[目标] dist[i][j] - 1dist[目标]dist[i][j]−1保证是最短路径上的下一步在满足上述条件的所有候选方向中按照题目规则选择最优的优先选择目标位置最北的行号最小如果行号相同选择最西的列号最小。注意这里比较的是目标位置的坐标而不是方向本身。这符合题意当路径长度相同时比较的是第一步到达的位置。第三步处理无法到达的位置对于dist[i][j]−1dist[i][j] -1dist[i][j]−1的位置直接标记为X。第四步输出最后按照格式输出字符矩阵即可。复杂度分析时间复杂度BFS\texttt{BFS}BFS过程中对于每个出队的点我们需要遍历同一行和同一列的所有点因此最坏情况下的时间复杂度为O(R×C×(RC))O(R \times C \times (R C))O(R×C×(RC))。在R,C≤50R, C \leq 50R,C≤50的情况下这是完全可以接受的约503125,00050^3 125,000503125,000次操作。空间复杂度O(R×C)O(R \times C)O(R×C)用于存储距离矩阵和方向矩阵。注意事项反向BFS\texttt{BFS}BFS是本题的核心思想可以避免为每个位置都进行一次正向搜索。方向选择时必须严格按照“最北、最西”的优先级进行比较而不是简单地按照N,W,S,E\texttt{N,W,S,E}N,W,S,E的顺序尝试。输入可能包含多个测试用例记得处理到0 00\ 000结束。参考代码// Grasshopper// UVa ID: 11705// Verdict: Accepted// Submission Date: 2026-02-25// UVa Run Time: 0.000s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structPoint{intr,c;Point(intr,intc):r(r),c(c){}};intmain(){introws,cols;while(cinrowscols(rows||cols)){vectorvectorintgrid(rows,vectorint(cols));for(inti0;irows;i)for(intj0;jcols;j)cingrid[i][j];// BFS 从出口开始反向搜索vectorvectorintdist(rows,vectorint(cols,-1));vectorvectorchardirection(rows,vectorchar(cols,X));queuePointq;// 出口位置dist[0][0]0;direction[0][0]*;q.push(Point(0,0));while(!q.empty()){Point pq.front();q.pop();// 检查同一列上哪些点可以跳到 pfor(intr0;rrows;r){if(rp.r)continue;if(abs(r-p.r)grid[r][p.c]dist[r][p.c]-1){dist[r][p.c]dist[p.r][p.c]1;q.push(Point(r,p.c));}}// 检查同一行上哪些点可以跳到 pfor(intc0;ccols;c){if(cp.c)continue;if(abs(c-p.c)grid[p.r][c]dist[p.r][c]-1){dist[p.r][c]dist[p.r][p.c]1;q.push(Point(p.r,c));}}}// 确定每个位置的方向for(inti0;irows;i){for(intj0;jcols;j){if(i0j0)continue;if(dist[i][j]-1){direction[i][j]X;continue;}intbestRrows,bestCcols;charbestDirX;intvalgrid[i][j];// 北方向跳到 (i - val, j)if(i-val0dist[i-val][j]dist[i][j]-1){if(i-valbestR||(i-valbestRjbestC)){bestRi-val;bestCj;bestDirN;}}// 西方向跳到 (i, j - val)if(j-val0dist[i][j-val]dist[i][j]-1){if(ibestR||(ibestRj-valbestC)){bestRi;bestCj-val;bestDirW;}}// 南方向跳到 (i val, j)if(ivalrowsdist[ival][j]dist[i][j]-1){if(ivalbestR||(ivalbestRjbestC)){bestRival;bestCj;bestDirS;}}// 东方向跳到 (i, j val)if(jvalcolsdist[i][jval]dist[i][j]-1){if(ibestR||(ibestRjvalbestC)){bestRi;bestCjval;bestDirE;}}direction[i][j]bestDir;}}// 输出结果for(inti0;irows;i){for(intj0;jcols;j)coutdirection[i][j];coutendl;}coutendl;}return0;}