题目描述

给定一个由单元格组成的矩形迷宫，每个单元格的四面（北、南、东、西）可能有墙。迷宫中有一个起点和一个终点，保证存在从起点到终点的唯一路径。机器人从起点出发，按照西、北、东、南的优先级顺序尝试移动，移动条件为：

(a)(a)(a)目标方向没有墙阻挡；
(b)(b)(b)目标单元格尚未被访问过。

当机器人到达终点时停止。若某单元格无法继续前进，则回退到上一个单元格，并尝试下一个未试的方向。

你的任务是模拟机器人的搜索过程，输出迷宫图形，其中：

• 起点标号为1；
• 路径上的每个单元格（包括终点）按访问顺序标号；
• 被访问过但不在最终路径上的单元格标记为???；
• 未访问的单元格留空（三个空格）。

输入中每个单元格的墙信息由整数给出（000到333），其中数值表示东墙（111）和南墙（222）的有无（二者相加）。例如，000表示无东墙无南墙；333表示既有东墙又有南墙。外边界墙隐含存在，不输入。

输入格式

每组数据第一行包含六个整数：前两个为迷宫的行数RRR和列数CCC（1≤R,C≤121 \le R,C \le 121≤R,C≤12），接下来两个为起点的行号和列号，最后两个为终点的行号和列号。随后有R×CR \times CR×C个整数，按行优先顺序给出每个单元格的墙信息。输入以六个0结束。

输出格式

对于每组数据，首先输出Maze X（XXX为编号，从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）即可，而无需显式栈模拟。关键在于：

1. 根据墙信息判断某个方向是否可通行。
2. 搜索时按指定顺序尝试移动。
3. 区分访问但不在最终路径上的单元格和路径上的单元格。

最终路径可通过回溯父节点的方式获得，然后将路径上的单元格标号，其他已访问的保持???。

解题思路

数据结构与方向映射

• 使用二维数组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），则目标列j+1必须≤C\le C≤C，且当前单元格maze[i][j]的东墙为000。
• 若d为南（SOUTH），则目标行i+1必须≤R\le R≤R，且当前单元格maze[i][j]的南墙为000。

DFS\texttt{DFS}DFS搜索

dfs(i, j)返回布尔值，表示从(i, j)能否到达终点。执行过程：

1. 标记visited[i][j] = -1（已访问）。
2. 若(i, j)为终点，返回true。
3. 按顺序遍历四个方向，对每个方向：
   • 计算下一步坐标(ni, nj)。
   • 若visited[ni][nj] == 0且可通行，则递归调用dfs(ni, nj)。
   • 若返回true，则记录path[ni][nj] = (i, j)，并返回true。
4. 若所有方向均失败，返回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//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constintWEST=0,NORTH=1,EAST=2,SOUTH=3;intmaze[20][20],visited[20][20];pair<int,int>path[20][20],offset[4]={{0,-1},{-1,0},{0,1},{1,0}};introws,columns,starti,startj,endi,endj;boolgo(inti,intj,intd){if(d==WEST&&(j==1||maze[i][j-1]==1||maze[i][j-1]==3))returnfalse;if(d==NORTH&&(i==1||maze[i-1][j]==2||maze[i-1][j]==3))returnfalse;if(d==EAST&&(j==columns||maze[i][j]==1||maze[i][j]==3))returnfalse;if(d==SOUTH&&(i==rows||maze[i][j]==2||maze[i][j]==3))returnfalse;returntrue;}booldfs(inti,intj){visited[i][j]=-1;if(i==endi&&j==endj)returntrue;for(intk=0;k<4;k++){intnexti=i+offset[k].first,nextj=j+offset[k].second;if(visited[nexti][nextj]==0&&go(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);intcases=0;while(cin>>rows>>columns>>starti>>startj>>endi>>endj){if(rows==0)break;for(inti=1;i<=rows;i++)for(intj=1;j<=columns;j++)cin>>maze[i][j];cout<<"Maze "<<++cases<<"\n\n";memset(visited,0,sizeof(visited));if(dfs(starti,startj)){vector<pair<int,int>>paths;pair<int,int>last(endi,endj);while(last.first!=starti||last.second!=startj){paths.push_back(last);last=path[last.first][last.second];}paths.push_back(make_pair(starti,startj));reverse(paths.begin(),paths.end());for(inti=0;i<paths.size();i++)visited[paths[i].first][paths[i].second]=i+1;}for(inti=1;i<=columns;i++)cout<<"+---";cout<<"+\n";for(inti=1;i<=rows;i++){if(i>1){for(intj=1;j<=columns;j++){cout<<'+';if(maze[i-1][j]==2||maze[i-1][j]==3)cout<<"---";elsecout<<" ";}cout<<"+\n";}for(intj=1;j<=columns;j++){if(j==1)cout<<'|';if(visited[i][j]==-1)cout<<"???";elseif(visited[i][j]==0)cout<<" ";elsecout<<setw(3)<<right<<visited[i][j];if(maze[i][j]==1||maze[i][j]==3||j==columns)cout<<'|';elsecout<<' ';}cout<<'\n';}for(inti=1;i<=columns;i++)cout<<"+---";cout<<"+\n";cout<<"\n\n";}return0;}

总结

本题通过深度优先搜索模拟机器人按固定优先级探索迷宫，并利用回溯记录路径。关键点包括：

• 正确理解墙信息的编码（东墙和南墙）。
• 实现方向移动的可通行性检查，注意外边界隐式墙。
• 利用path数组回溯构建路径，并区分路径与非路径已访问单元格。
• 输出迷宫图形时精确控制空格和分隔符，尤其是单元格内容的对齐和墙的绘制。

该解法简洁高效，适用于小规模迷宫，也体现了深度优先搜索在路径寻找中的典型应用。