题目描述一张数字化地图由二维网格表示地图由轮廓线包围的一组点构成。地图的闭合轮廓可为任意矩形形状和轮廓内部的障碍物均用字符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的方法对解决类似迷宫最优路径问题具有普遍意义。
企业数字化 ERP 产品动态
相关推荐
WAIC 2026倒计时!来沐曦股份开源专区打卡十大社区,赢限定周边! /* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/21 9:25:57
几种常用防反接电路设计 防反接电路1.二极管防反接1.1 前向回路串联肖特基二极管1.2 并联二极管自恢复保险丝接反时二极管导通,电路短路,自恢复保险丝断。2.PMOS防反接2.1串联PMOS: · 2026/11/10 13:40:13
【C++】外部接口封装关键字extern /* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/11 8:32:43
工地太忙根本没时间复习考试,京都职业学校电工证值不值得考? 工地太忙根本没时间复习考试,京都职业学校电工证值不值得考? 工地太忙根本没时间复习考试,很多人心里都在打鼓:京都职业学校电工证值不值得考?如果你是电工,又在一线施工,那这证不仅值得考,而且是 必须考… · 2026/11/21 9:25:16
鹤壁电工证去哪里报考多久拿证全攻略 鹤壁电工证去哪里报考多久拿证全攻略 实操考试心里没底怕挂科,是很多想考电工证的朋友最真实的感受。尤其是对于第一次接触特种作业考试的人来说,面对复杂的考试流程、严格的实操标准,难免会感到紧张和焦虑。别担心,这篇文章会从【鹤壁电工证去哪里报考】… · 2026/11/21 9:25:16
低压电工证计算题技巧通过率揭秘:学历不高也能轻松拿证 低压电工证计算题技巧通过率揭秘:学历不高也能轻松拿证 你是不是总担心自己学历不高,连低压电工证都报不了名?别急,我今天就给你讲讲怎么用【低压电工证计算题技巧】提高通过率,让你顺利拿到证书,不靠“聪明”,靠的是“技巧”。… · 2026/11/21 9:25:16
徐辛庄电工证培训怎么选?郑州报考避坑指南全在这了 徐辛庄电工证培训怎么选?郑州报考避坑指南全在这了 证书过期了不知道怎么复审延期?这事儿你不是一个人。很多在徐辛庄、郑州一带从事电工工作的朋友,因为工作繁忙或信息不对称,经常遇到证书过期、不知道如何复审的问题。今天我们就从 徐辛庄电工证培训… · 2026/11/21 9:25:16
考电工证什么流程最难 外省证能转吗电子证书怎么用 考电工证什么流程最难 外省证能转吗电子证书怎么用 之前考的证在外省能不能转过来,这个问题其实困扰了不少像你我一样的从业者,特别是那些在外省打拼的小伙伴。很多人拿着外省的 电子证书… · 2026/11/21 9:25:16
长春初级电工证怎么考?通过率揭秘全在这里 长春初级电工证怎么考?通过率揭秘全在这里 之前考的证在外省能不能转过来?这几乎是每个想从事电工工作的人都会问的问题。特别是那些在外地打拼多年、手里握着一张“外地电工证”的人,到了长春想继续干这一行,第一反应就是“我的证能用吗?”。今天我们就… · 2026/11/20 16:18:19
国内电工证报考条件与考试时间 低压电工证怎么考?学历不高也能报名,官方报名入口全在这 你是不是经常听说“电工证是入行门槛”,但又担心自己学历不够、经验不足,根本报不了名?别急,今天就带你从零了解【国内电工证】的报考流程、考试内容,还有怎么在 官方报名入口… · 2026/11/20 18:25:07
电工作业时如何断电?电子证书到底能不能全国通用? 电工作业时如何断电?电子证书到底能不能全国通用? 实操考试心里没底怕挂科,特别是电工作业时如何断电这一操作,不仅关系到你能不能拿到证书,更关系到以后能不能顺利上岗。很多人觉得这不过就是“断个电”,但其实这里面的门道可不少,稍有不慎就可能出错… · 2026/11/20 17:56:32
电工证征求意见2026河南最新政策怎么应对?学历不高也能考! 电工证征求意见2026河南最新政策怎么应对?学历不高也能考! 你是不是也担心自己学历不高, 怕报不上名 ?尤其是像焦作水利工程这样的从业者,常年在一线作业,但证书却成了晋升、转岗、接项目的关键门槛。 2026河南最新政策… · 2026/11/21 0:00:17
电工证征求意见怎么填?含金量高不高?济源电工朋友看过来 电工证征求意见怎么填?含金量高不高?济源电工朋友看过来 不知道去哪报名怕被中介坑,电工证征求意见填错了不仅白费钱,还可能影响后续考试和工作。最近很多济源的电工朋友都在问: 电工证征求意见怎么填… · 2026/11/21 0:00:17
房建企业特种工考前押题怎么找?别让培训费打了水漂 房建企业特种工考前押题怎么找?别让培训费打了水漂 怕考不过白交培训费?房建企业特种工考试难度高、题型多,很多人报名后才发现没有合适的复习资料,最终考试落榜,白白浪费了时间和金钱。别担心,掌握【考前押题】的技巧,能让你事半功倍,顺利通过考试。… · 2026/11/21 0:00:17
双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试 /* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/20 10:25:45
STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析 /* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/20 10:25:54
DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案 /* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/20 10:26:03