UVa 614 Mapping the Route

题目描述给定一个由单元格组成的矩形迷宫每个单元格的四面北、南、东、西可能有墙。迷宫中有一个起点和一个终点保证存在从起点到终点的唯一路径。机器人从起点出发按照西、北、东、南的优先级顺序尝试移动移动条件为(a)(a)(a)目标方向没有墙阻挡(b)(b)(b)目标单元格尚未被访问过。当机器人到达终点时停止。若某单元格无法继续前进则回退到上一个单元格并尝试下一个未试的方向。你的任务是模拟机器人的搜索过程输出迷宫图形其中起点标号为1路径上的每个单元格包括终点按访问顺序标号被访问过但不在最终路径上的单元格标记为???未访问的单元格留空三个空格。输入中每个单元格的墙信息由整数给出000到333其中数值表示东墙111和南墙222的有无二者相加。例如000表示无东墙无南墙333表示既有东墙又有南墙。外边界墙隐含存在不输入。输入格式每组数据第一行包含六个整数前两个为迷宫的行数RRR和列数CCC1≤R,C≤121 \le R,C \le 121≤R,C≤12接下来两个为起点的行号和列号最后两个为终点的行号和列号。随后有R×CR \times CR×C个整数按行优先顺序给出每个单元格的墙信息。输入以六个0结束。输出格式对于每组数据首先输出Maze XXXX为编号从111开始然后空一行。接着以样例格式输出迷宫图形其中顶部和底部边框由---重复CCC次后加组成行间分隔符左中间根据上一行单元格的南墙决定---或 右每行内容左边界|每个单元格输出三字符内容路径编号右对齐占333位或???或三个空格然后根据当前单元格是否有东墙输出|或空格。每组输出后打印两个空行。样例输入2 3 1 1 1 3 1 1 0 0 0 0 4 3 3 2 4 3 0 3 0 0 2 0 0 3 0 0 1 0 0 0 0 0 0 0输出Maze 1 --------- | 1|???| 5| | 2 3 4| --------- Maze 2 --------- |??? ???|???| --- | 3 4 5| --- | 2 1| 6| --- | | 7| ---------题目分析本题的核心是模拟机器人在迷宫中的搜索过程并输出带标注的迷宫图。搜索顺序固定为西、北、东、南且禁止重复访问因此搜索路径是唯一的在给定规则下。我们需要忠实地模拟这一过程记录访问状态和路径。由于迷宫尺寸很小R,C≤12R,C \le 12R,C≤12使用深度优先搜索DFS\texttt{DFS}DFS即可而无需显式栈模拟。关键在于根据墙信息判断某个方向是否可通行。搜索时按指定顺序尝试移动。区分访问但不在最终路径上的单元格和路径上的单元格。最终路径可通过回溯父节点的方式获得然后将路径上的单元格标号其他已访问的保持???。解题思路数据结构与方向映射使用二维数组maze[20][20]存储墙信息下标从111开始。visited[20][20]存储状态000未访问−1-1−1已访问但不在路径正数表示路径顺序。path[20][20]存储父节点坐标用于回溯。方向顺序为西、北、东、南对应偏移量(0, -1), (-1, 0), (0, 1), (1, 0)。可移动性判断函数go(i, j, d)判断从(i, j)沿方向d移动是否可行若d为西WEST则目标列j-1必须≥1\ge 1≥1且当前单元格左侧的墙信息中东墙为000。注意左侧单元格的东墙即当前单元格的西墙但输入只给每个单元格的东墙和南墙因此检查maze[i][j-1]是否包含东墙111或333。若d为北NORTH则目标行i-1必须≥1\ge 1≥1且上方单元格maze[i-1][j]的南墙为000即不含222或333。若d为东EAST则目标列j1必须≤C\le C≤C且当前单元格maze[i][j]的东墙为000。若d为南SOUTH则目标行i1必须≤R\le R≤R且当前单元格maze[i][j]的南墙为000。DFS\texttt{DFS}DFS搜索dfs(i, j)返回布尔值表示从(i, j)能否到达终点。执行过程标记visited[i][j] -1已访问。若(i, j)为终点返回true。按顺序遍历四个方向对每个方向计算下一步坐标(ni, nj)。若visited[ni][nj] 0且可通行则递归调用dfs(ni, nj)。若返回true则记录path[ni][nj] (i, j)并返回true。若所有方向均失败返回false。路径标号与输出从终点开始利用path反向回溯至起点将坐标存入临时向量然后反转得到从起点到终点的顺序。遍历该向量将对应visited设为顺序号从111开始。输出迷宫图形时对每个单元格若visited为−1-1−1输出???。若visited为正数用setw(3)右对齐输出该数。否则输出三个空格。墙的绘制依据maze中的东墙和南墙信息以及外边界隐式墙。输出格式细节顶部边框---重复CCC次后加。行间分隔从第二行开始先输出然后对于每列若上一行当前列有南墙则输出---否则输出 最后以结束。每行内容先输出|然后对于每列输出三字符内容再根据当前单元格是否有东墙或是否最后一列输出|或空格。底部边框同顶部。每组数据输出后有两个空行。复杂度分析每个单元格最多被访问一次DFS\texttt{DFS}DFS时间复杂度O(R⋅C)O(R \cdot C)O(R⋅C)。回溯路径和输出均为O(R⋅C)O(R \cdot C)O(R⋅C)。空间复杂度O(R⋅C)O(R \cdot C)O(R⋅C)。代码实现// Mapping the Route// UVa ID: 614// Verdict: Accepted// Submission Date: 2016-08-31// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintWEST0,NORTH1,EAST2,SOUTH3;intmaze[20][20],visited[20][20];pairint,intpath[20][20],offset[4]{{0,-1},{-1,0},{0,1},{1,0}};introws,columns,starti,startj,endi,endj;boolgo(inti,intj,intd){if(dWEST(j1||maze[i][j-1]1||maze[i][j-1]3))returnfalse;if(dNORTH(i1||maze[i-1][j]2||maze[i-1][j]3))returnfalse;if(dEAST(jcolumns||maze[i][j]1||maze[i][j]3))returnfalse;if(dSOUTH(irows||maze[i][j]2||maze[i][j]3))returnfalse;returntrue;}booldfs(inti,intj){visited[i][j]-1;if(iendijendj)returntrue;for(intk0;k4;k){intnextiioffset[k].first,nextjjoffset[k].second;if(visited[nexti][nextj]0go(i,j,k)){visited[nexti][nextj]-1;if(dfs(nexti,nextj)){path[nexti][nextj]make_pair(i,j);returntrue;}}}returnfalse;}intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intcases0;while(cinrowscolumnsstartistartjendiendj){if(rows0)break;for(inti1;irows;i)for(intj1;jcolumns;j)cinmaze[i][j];coutMaze cases\n\n;memset(visited,0,sizeof(visited));if(dfs(starti,startj)){vectorpairint,intpaths;pairint,intlast(endi,endj);while(last.first!starti||last.second!startj){paths.push_back(last);lastpath[last.first][last.second];}paths.push_back(make_pair(starti,startj));reverse(paths.begin(),paths.end());for(inti0;ipaths.size();i)visited[paths[i].first][paths[i].second]i1;}for(inti1;icolumns;i)cout---;cout\n;for(inti1;irows;i){if(i1){for(intj1;jcolumns;j){cout;if(maze[i-1][j]2||maze[i-1][j]3)cout---;elsecout ;}cout\n;}for(intj1;jcolumns;j){if(j1)cout|;if(visited[i][j]-1)cout???;elseif(visited[i][j]0)cout ;elsecoutsetw(3)rightvisited[i][j];if(maze[i][j]1||maze[i][j]3||jcolumns)cout|;elsecout ;}cout\n;}for(inti1;icolumns;i)cout---;cout\n;cout\n\n;}return0;}总结本题通过深度优先搜索模拟机器人按固定优先级探索迷宫并利用回溯记录路径。关键点包括正确理解墙信息的编码东墙和南墙。实现方向移动的可通行性检查注意外边界隐式墙。利用path数组回溯构建路径并区分路径与非路径已访问单元格。输出迷宫图形时精确控制空格和分隔符尤其是单元格内容的对齐和墙的绘制。该解法简洁高效适用于小规模迷宫也体现了深度优先搜索在路径寻找中的典型应用。