题目描述一张数字化地图由二维网格表示地图由轮廓线包围的一组点构成。地图的闭合轮廓可为任意矩形形状和轮廓内部的障碍物均用字符X标记地图中的空闲点用空格表示。地图上恰好有两个起点 / 终点用字符标记。起点 / 终点不能出现在地图外部或轮廓线上。地图中除空闲点空格、障碍物X和起点 / 终点外没有其他点。两点之间的路径只能垂直和 / 或水平穿过地图内部的空闲点在地图轮廓内。路径的长度为路径经过的点数包括起点和终点。路径的转弯次数为遍历路径时方向改变的次数。编写程序对于从文本文件中读取的每张地图找出所有可能的最短路径长度最短中转弯次数最少的路径并用字符#标记这些路径上的点。输入格式每个测试用例包含一张地图由若干行组成每行最多808080个字符地图行数不超过404040。地图中只包含字符X、空格、。地图的轮廓由X围成且轮廓为矩形。地图内可以包含若干障碍物X。每张地图以一行全由下划线_组成的行结束。各行长度可能不同输入数据保证正确。输出格式对于每张地图先输出一行统计信息格式为路径数 paths, 点数 points, 转弯数 turns其中点数是最短路径的长度含起点和终点转弯数是这些最优路径的转弯次数。之后输出地图将属于所有最优路径上的点标记为#但起点和终点仍保留为。地图格式与输入相同包括终止行。样例样例输入XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX X X X X X X X X XXXXXX X X X X X X X XXXXXX X X X XXXXXXXXXXXXXXXXXXXXXXXXX ______________________________ XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX X X X XXXXXX XXXXXXXXXXXXXXXXXXXXXXXXX ______________________________样例输出6 paths, 32 points, 3 turns XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX X X############# X X ### X # X X ##################### X XXXXXX### ###X X X###############X X X# ###X XXXXXX X#######X X XXXXXXXXXXXXXXXXXXXXXXXXX ______________________________ 1 paths, 2 points, 0 turns XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX X X X XXXXXX XXXXXXXXXXXXXXXXXXXXXXXXX ______________________________题目分析本题要求在地图上找出所有长度最短的路径并从中筛选出转弯次数最少的路径最后标记这些路径。这是一个典型的多目标优化问题且需要输出所有满足条件的路径上的点而不仅仅是路径数量。地图规模为40×8040 \times 8040×80的网格点数最多320032003200状态空间较小可以使用动态规划结合广度优先搜索来处理。关键点包括路径只能在空闲格非X上移动且不能越界。最短路径长度可通过从起点到终点的BFS\texttt{BFS}BFS获得。在保证路径长度最短的前提下需要最小化转弯次数。需要统计达到最优最短长度 最少转弯的路径条数并标记这些路径上的所有点。直接枚举所有最短路径会指数爆炸因此需要设计高效的状态转移和回溯方法。解题思路第一步读入与网格规范化逐行读入地图当遇到全由下划线组成的行时认为当前地图结束。将地图行存储为字符串列表由于各行长度可能不同需要统一补齐到最大宽度用空格填充以便后续二维数组操作。第二步计算最短距离长度从起点出发执行BFS\texttt{BFS}BFS广度优先搜索计算到每个可达空格的最短步数即经过的边数。终点处的步数记为SSS则最短路径的点数为S1S 1S1因为步数 点数− 1- \ 1−1。只有位于该最短距离层次上的点才可能属于最优路径。第三步动态规划求最少转弯次数与路径计数由于我们只关心最短路径所以任何转移都只能从距离为ddd的格点走到距离为d1d1d1的相邻格点。定义状态为(r, c, d)其中(r, c)是当前格点坐标d表示进入该格点时的方向000上111下222左333右。状态的含义是在满足从起点到(r, c)的距离等于dist[r][c]\textit{dist}[r][c]dist[r][c]的前提下到达该状态的最小转弯次数。令turn[r][c][dir]表示状态(r, c, dir)的最小转弯次数ways[r][c][dir]表示达到该最小转弯次数的路径条数。初始化从起点出发到相邻格点距离为111的四个状态转弯次数为000路径条数为111因为从起点直接走一步没有转弯。然后按距离从小到大进行状态转移。对于每个状态(r, c, dir)尝试向四个方向nd移动一步到达新格点(nr, nc)要求dist[nr][nc] dist[r][c] 1。新的转弯次数为turn[r][c][dir] (dir ! nd ? 1 : 0)。如果小于turn[nr][nc][nd]则更新并设置路径数为当前ways如果相等则将当前ways累加到目标状态。注意这里每个格点可能有多个不同方向的状态分别存储了从不同方向进入该点时的最优值这样能够正确处理转弯的计数。第四步统计最优结果终点(er, ec)的最少转弯次数为minTurns min(turn[er][ec][d])总路径数为所有达到minTurns的状态的ways之和。第五步反向回溯标记所有最优路径上的点为了标记所有最优路径上的点需要从终点的所有最优状态出发反向寻找前驱状态。前驱状态(pr, pc, pd)必须满足dist[pr][pc] dist[r][c] - 1即前驱距离少111。状态可达即turn[pr][pc][pd]有限。转移代价满足turn[pr][pc][pd] (pd ! d ? 1 : 0) turn[r][c][d]。使用一个栈或队列进行深度优先回溯标记所有访问过的格点。注意需要避免重复访问同一状态使用visited三维布尔数组。回溯时如果到达起点直接标记起点即可起点最终保留为但为了回溯完整性也进行标记。第六步输出先输出统计行然后逐行输出地图。对于每个格点如果原始字符是则输出否则如果被标记为路径点则输出#否则输出原始字符可能是空格或X。最后输出终止行。复杂度分析BFS\texttt{BFS}BFSO(R⋅C)O(R \cdot C)O(R⋅C)。DP\texttt{DP}DP转移对每个格点的每个方向444种尝试向444个方向转移故O(R⋅C⋅4⋅4)O(R⋅C)O(R \cdot C \cdot 4 \cdot 4) O(R \cdot C)O(R⋅C⋅4⋅4)O(R⋅C)。回溯标记每个状态最多被访问一次O(R⋅C⋅4)O(R \cdot C \cdot 4)O(R⋅C⋅4)。总时间复杂度O(R⋅C)O(R \cdot C)O(R⋅C)空间复杂度O(R⋅C⋅4)O(R \cdot C \cdot 4)O(R⋅C⋅4)。其中R≤40R \le 40R≤40C≤80C \le 80C≤80完全可行。代码实现// Straightest Paths// UVa ID: 794// Verdict: Accepted// Submission Date: 2026-07-08// UVa Run Time: 0.100s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structState{intr,c,d;};voidsolveMap(constvectorstringmapLines,conststringtermLine){if(mapLines.empty())return;constintR(int)mapLines.size();intC0;for(conststrings:mapLines)Cmax(C,(int)s.size());vectorstringgrid(R,string(C, ));for(inti0;iR;i)for(intj0;j(int)mapLines[i].size();j)grid[i][j]mapLines[i][j];intsr-1,sc-1,er-1,ec-1;for(inti0;iR;i)for(intj0;jC;j)if(grid[i][j]){if(sr-1){sri;scj;}else{eri;ecj;}}constintdr[4]{-1,1,0,0};constintdc[4]{0,0,-1,1};// BFS 求最短距离步数vectorvectorintdist(R,vectorint(C,-1));queuepairint,intq;dist[sr][sc]0;q.push({sr,sc});while(!q.empty()){pairint,intcurq.front();q.pop();intrcur.first,ccur.second;for(intd0;d4;d){intnrrdr[d],nccdc[d];if(nr0||nrR||nc0||ncC)continue;if(grid[nr][nc]X)continue;if(dist[nr][nc]-1){dist[nr][nc]dist[r][c]1;q.push({nr,nc});}}}intshortestDistdist[er][ec];intpointsshortestDist1;constintINF1e9;vectorvectorvectorintturn(R,vectorvectorint(C,vectorint(4,INF)));vectorvectorvectorlonglongways(R,vectorvectorlonglong(C,vectorlonglong(4,0)));// 从起点出发的第一步for(intd0;d4;d){intnrsrdr[d],ncscdc[d];if(nr0||nrR||nc0||ncC)continue;if(grid[nr][nc]X)continue;if(dist[nr][nc]1){turn[nr][nc][d]0;ways[nr][nc][d]1;}}// DP 按距离递增for(intstep1;stepshortestDist;step){for(intr0;rR;r)for(intc0;cC;c){if(dist[r][c]!step)continue;for(intd0;d4;d){if(turn[r][c][d]INF)continue;intcurTurnturn[r][c][d];longlongcurWaysways[r][c][d];for(intnd0;nd4;nd){intnrrdr[nd],nccdc[nd];if(nr0||nrR||nc0||ncC)continue;if(grid[nr][nc]X)continue;if(dist[nr][nc]!dist[r][c]1)continue;intnewTurncurTurn(nd!d?1:0);if(newTurnturn[nr][nc][nd]){turn[nr][nc][nd]newTurn;ways[nr][nc][nd]curWays;}elseif(newTurnturn[nr][nc][nd]){ways[nr][nc][nd]curWays;}}}}}// 统计终点的最优值intminTurnsINF;longlongtotalPaths0;for(intd0;d4;d){if(turn[er][ec][d]minTurns){minTurnsturn[er][ec][d];totalPathsways[er][ec][d];}elseif(turn[er][ec][d]minTurns){totalPathsways[er][ec][d];}}// 标记所有最优路径上的点vectorvectorboolmark(R,vectorbool(C,false));vectorvectorvectorboolvisited(R,vectorvectorbool(C,vectorbool(4,false)));vectorStatest;for(intd0;d4;d)if(turn[er][ec][d]minTurns!visited[er][ec][d]){visited[er][ec][d]true;st.push_back({er,ec,d});}while(!st.empty()){State curst.back();st.pop_back();intrcur.r,ccur.c,dcur.d;mark[r][c]true;if(rsrcsc)continue;intprr-dr[d],pcc-dc[d];if(pr0||prR||pc0||pcC)continue;if(grid[pr][pc]X)continue;if(dist[pr][pc]!dist[r][c]-1)continue;for(intpd0;pd4;pd){if(turn[pr][pc][pd]INF)continue;intcost(pd!d?1:0);if(turn[pr][pc][pd]costturn[r][c][d]){if(prsrpcsc){mark[pr][pc]true;}elseif(!visited[pr][pc][pd]){visited[pr][pc][pd]true;st.push_back({pr,pc,pd});}}}}// 输出couttotalPaths paths, points points, minTurns turns\n;for(inti0;iR;i){string out;for(intj0;jC;j){if(grid[i][j])out;elseif(mark[i][j])out#;elseoutgrid[i][j];}while(out.size()out.back() )out.pop_back();coutout\n;}couttermLine\n;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);string line;vectorstringmapLines;while(getline(cin,line)){boolisTermtrue;for(charch:line)if(ch!_){isTermfalse;break;}if(isTerm){solveMap(mapLines,line);mapLines.clear();}elsemapLines.push_back(line);}return0;}总结本题综合运用了BFS\texttt{BFS}BFS求最短距离、动态规划求多目标最优值以及反向回溯标记所有最优路径。核心技巧是将方向信息引入状态使得转弯次数的计算得以在最短路径约束下正确进行。同时通过ways数组累计路径条数并利用visited避免重复回溯高效标记所有公共点。该解法适用于小规模网格40×8040 \times 8040×80时空开销都在可接受范围内。如果地图规模扩大可以考虑对状态进行压缩但本题无需额外优化。掌握这种状态扩展 多目标DP\texttt{DP}DP的方法对解决类似迷宫最优路径问题具有普遍意义。 
长河君 · 2026/10/30 2:00:41 · 阅读 1.2k UVa 794 Straightest Paths
题目描述一张数字化地图由二维网格表示地图由轮廓线包围的一组点构成。地图的闭合轮廓可为任意矩形形状和轮廓内部的障碍物均用字符X标记地图中的空闲点用空格表示。地图上恰好有两个起点 / 终点用字符标记。起点 / 终点不能出现在地图外部或轮廓线上。地图中除空闲点空格、障碍物X和起点 / 终点外没有其他点。两点之间的路径只能垂直和 / 或水平穿过地图内部的空闲点在地图轮廓内。路径的长度为路径经过的点数包括起点和终点。路径的转弯次数为遍历路径时方向改变的次数。编写程序对于从文本文件中读取的每张地图找出所有可能的最短路径长度最短中转弯次数最少的路径并用字符#标记这些路径上的点。输入格式每个测试用例包含一张地图由若干行组成每行最多808080个字符地图行数不超过404040。地图中只包含字符X、空格、。地图的轮廓由X围成且轮廓为矩形。地图内可以包含若干障碍物X。每张地图以一行全由下划线_组成的行结束。各行长度可能不同输入数据保证正确。输出格式对于每张地图先输出一行统计信息格式为路径数 paths, 点数 points, 转弯数 turns其中点数是最短路径的长度含起点和终点转弯数是这些最优路径的转弯次数。之后输出地图将属于所有最优路径上的点标记为#但起点和终点仍保留为。地图格式与输入相同包括终止行。样例样例输入XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX X X X X X X X X XXXXXX X X X X X X X XXXXXX X X X XXXXXXXXXXXXXXXXXXXXXXXXX ______________________________ XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX X X X XXXXXX XXXXXXXXXXXXXXXXXXXXXXXXX ______________________________样例输出6 paths, 32 points, 3 turns XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX X X############# X X ### X # X X ##################### X XXXXXX### ###X X X###############X X X# ###X XXXXXX X#######X X XXXXXXXXXXXXXXXXXXXXXXXXX ______________________________ 1 paths, 2 points, 0 turns XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX X X X XXXXXX XXXXXXXXXXXXXXXXXXXXXXXXX ______________________________题目分析本题要求在地图上找出所有长度最短的路径并从中筛选出转弯次数最少的路径最后标记这些路径。这是一个典型的多目标优化问题且需要输出所有满足条件的路径上的点而不仅仅是路径数量。地图规模为40×8040 \times 8040×80的网格点数最多320032003200状态空间较小可以使用动态规划结合广度优先搜索来处理。关键点包括路径只能在空闲格非X上移动且不能越界。最短路径长度可通过从起点到终点的BFS\texttt{BFS}BFS获得。在保证路径长度最短的前提下需要最小化转弯次数。需要统计达到最优最短长度 最少转弯的路径条数并标记这些路径上的所有点。直接枚举所有最短路径会指数爆炸因此需要设计高效的状态转移和回溯方法。解题思路第一步读入与网格规范化逐行读入地图当遇到全由下划线组成的行时认为当前地图结束。将地图行存储为字符串列表由于各行长度可能不同需要统一补齐到最大宽度用空格填充以便后续二维数组操作。第二步计算最短距离长度从起点出发执行BFS\texttt{BFS}BFS广度优先搜索计算到每个可达空格的最短步数即经过的边数。终点处的步数记为SSS则最短路径的点数为S1S 1S1因为步数 点数− 1- \ 1−1。只有位于该最短距离层次上的点才可能属于最优路径。第三步动态规划求最少转弯次数与路径计数由于我们只关心最短路径所以任何转移都只能从距离为ddd的格点走到距离为d1d1d1的相邻格点。定义状态为(r, c, d)其中(r, c)是当前格点坐标d表示进入该格点时的方向000上111下222左333右。状态的含义是在满足从起点到(r, c)的距离等于dist[r][c]\textit{dist}[r][c]dist[r][c]的前提下到达该状态的最小转弯次数。令turn[r][c][dir]表示状态(r, c, dir)的最小转弯次数ways[r][c][dir]表示达到该最小转弯次数的路径条数。初始化从起点出发到相邻格点距离为111的四个状态转弯次数为000路径条数为111因为从起点直接走一步没有转弯。然后按距离从小到大进行状态转移。对于每个状态(r, c, dir)尝试向四个方向nd移动一步到达新格点(nr, nc)要求dist[nr][nc] dist[r][c] 1。新的转弯次数为turn[r][c][dir] (dir ! nd ? 1 : 0)。如果小于turn[nr][nc][nd]则更新并设置路径数为当前ways如果相等则将当前ways累加到目标状态。注意这里每个格点可能有多个不同方向的状态分别存储了从不同方向进入该点时的最优值这样能够正确处理转弯的计数。第四步统计最优结果终点(er, ec)的最少转弯次数为minTurns min(turn[er][ec][d])总路径数为所有达到minTurns的状态的ways之和。第五步反向回溯标记所有最优路径上的点为了标记所有最优路径上的点需要从终点的所有最优状态出发反向寻找前驱状态。前驱状态(pr, pc, pd)必须满足dist[pr][pc] dist[r][c] - 1即前驱距离少111。状态可达即turn[pr][pc][pd]有限。转移代价满足turn[pr][pc][pd] (pd ! d ? 1 : 0) turn[r][c][d]。使用一个栈或队列进行深度优先回溯标记所有访问过的格点。注意需要避免重复访问同一状态使用visited三维布尔数组。回溯时如果到达起点直接标记起点即可起点最终保留为但为了回溯完整性也进行标记。第六步输出先输出统计行然后逐行输出地图。对于每个格点如果原始字符是则输出否则如果被标记为路径点则输出#否则输出原始字符可能是空格或X。最后输出终止行。复杂度分析BFS\texttt{BFS}BFSO(R⋅C)O(R \cdot C)O(R⋅C)。DP\texttt{DP}DP转移对每个格点的每个方向444种尝试向444个方向转移故O(R⋅C⋅4⋅4)O(R⋅C)O(R \cdot C \cdot 4 \cdot 4) O(R \cdot C)O(R⋅C⋅4⋅4)O(R⋅C)。回溯标记每个状态最多被访问一次O(R⋅C⋅4)O(R \cdot C \cdot 4)O(R⋅C⋅4)。总时间复杂度O(R⋅C)O(R \cdot C)O(R⋅C)空间复杂度O(R⋅C⋅4)O(R \cdot C \cdot 4)O(R⋅C⋅4)。其中R≤40R \le 40R≤40C≤80C \le 80C≤80完全可行。代码实现// Straightest Paths// UVa ID: 794// Verdict: Accepted// Submission Date: 2026-07-08// UVa Run Time: 0.100s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structState{intr,c,d;};voidsolveMap(constvectorstringmapLines,conststringtermLine){if(mapLines.empty())return;constintR(int)mapLines.size();intC0;for(conststrings:mapLines)Cmax(C,(int)s.size());vectorstringgrid(R,string(C, ));for(inti0;iR;i)for(intj0;j(int)mapLines[i].size();j)grid[i][j]mapLines[i][j];intsr-1,sc-1,er-1,ec-1;for(inti0;iR;i)for(intj0;jC;j)if(grid[i][j]){if(sr-1){sri;scj;}else{eri;ecj;}}constintdr[4]{-1,1,0,0};constintdc[4]{0,0,-1,1};// BFS 求最短距离步数vectorvectorintdist(R,vectorint(C,-1));queuepairint,intq;dist[sr][sc]0;q.push({sr,sc});while(!q.empty()){pairint,intcurq.front();q.pop();intrcur.first,ccur.second;for(intd0;d4;d){intnrrdr[d],nccdc[d];if(nr0||nrR||nc0||ncC)continue;if(grid[nr][nc]X)continue;if(dist[nr][nc]-1){dist[nr][nc]dist[r][c]1;q.push({nr,nc});}}}intshortestDistdist[er][ec];intpointsshortestDist1;constintINF1e9;vectorvectorvectorintturn(R,vectorvectorint(C,vectorint(4,INF)));vectorvectorvectorlonglongways(R,vectorvectorlonglong(C,vectorlonglong(4,0)));// 从起点出发的第一步for(intd0;d4;d){intnrsrdr[d],ncscdc[d];if(nr0||nrR||nc0||ncC)continue;if(grid[nr][nc]X)continue;if(dist[nr][nc]1){turn[nr][nc][d]0;ways[nr][nc][d]1;}}// DP 按距离递增for(intstep1;stepshortestDist;step){for(intr0;rR;r)for(intc0;cC;c){if(dist[r][c]!step)continue;for(intd0;d4;d){if(turn[r][c][d]INF)continue;intcurTurnturn[r][c][d];longlongcurWaysways[r][c][d];for(intnd0;nd4;nd){intnrrdr[nd],nccdc[nd];if(nr0||nrR||nc0||ncC)continue;if(grid[nr][nc]X)continue;if(dist[nr][nc]!dist[r][c]1)continue;intnewTurncurTurn(nd!d?1:0);if(newTurnturn[nr][nc][nd]){turn[nr][nc][nd]newTurn;ways[nr][nc][nd]curWays;}elseif(newTurnturn[nr][nc][nd]){ways[nr][nc][nd]curWays;}}}}}// 统计终点的最优值intminTurnsINF;longlongtotalPaths0;for(intd0;d4;d){if(turn[er][ec][d]minTurns){minTurnsturn[er][ec][d];totalPathsways[er][ec][d];}elseif(turn[er][ec][d]minTurns){totalPathsways[er][ec][d];}}// 标记所有最优路径上的点vectorvectorboolmark(R,vectorbool(C,false));vectorvectorvectorboolvisited(R,vectorvectorbool(C,vectorbool(4,false)));vectorStatest;for(intd0;d4;d)if(turn[er][ec][d]minTurns!visited[er][ec][d]){visited[er][ec][d]true;st.push_back({er,ec,d});}while(!st.empty()){State curst.back();st.pop_back();intrcur.r,ccur.c,dcur.d;mark[r][c]true;if(rsrcsc)continue;intprr-dr[d],pcc-dc[d];if(pr0||prR||pc0||pcC)continue;if(grid[pr][pc]X)continue;if(dist[pr][pc]!dist[r][c]-1)continue;for(intpd0;pd4;pd){if(turn[pr][pc][pd]INF)continue;intcost(pd!d?1:0);if(turn[pr][pc][pd]costturn[r][c][d]){if(prsrpcsc){mark[pr][pc]true;}elseif(!visited[pr][pc][pd]){visited[pr][pc][pd]true;st.push_back({pr,pc,pd});}}}}// 输出couttotalPaths paths, points points, minTurns turns\n;for(inti0;iR;i){string out;for(intj0;jC;j){if(grid[i][j])out;elseif(mark[i][j])out#;elseoutgrid[i][j];}while(out.size()out.back() )out.pop_back();coutout\n;}couttermLine\n;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);string line;vectorstringmapLines;while(getline(cin,line)){boolisTermtrue;for(charch:line)if(ch!_){isTermfalse;break;}if(isTerm){solveMap(mapLines,line);mapLines.clear();}elsemapLines.push_back(line);}return0;}总结本题综合运用了BFS\texttt{BFS}BFS求最短距离、动态规划求多目标最优值以及反向回溯标记所有最优路径。核心技巧是将方向信息引入状态使得转弯次数的计算得以在最短路径约束下正确进行。同时通过ways数组累计路径条数并利用visited避免重复回溯高效标记所有公共点。该解法适用于小规模网格40×8040 \times 8040×80时空开销都在可接受范围内。如果地图规模扩大可以考虑对状态进行压缩但本题无需额外优化。掌握这种状态扩展 多目标DP\texttt{DP}DP的方法对解决类似迷宫最优路径问题具有普遍意义。