题目描述给定一个由交叉口组成的箭头迷宫每个交叉口有一个标志指示从某个方向进入时允许的转向方向左、前、右或它们的组合。迷宫尺寸最大为9×99 \times 99×9。给出起点、起点进入方向、终点要求找到从起点开始按给定方向进入迷宫后到达终点的最短路径并输出路径上的所有交叉口坐标。若不存在路径则输出No Solution Possible。输入格式每个迷宫描述以一行字符串迷宫名称开始。下一行包含起点行、起点列、起始方向、终点行、终点列。随后若干行每行格式为row col后跟一个或多个方向组如N L F最后以*结束。方向组中第一个字符为进入方向后续字符为允许的转向L、F、R。输入以行0结束整个输入以END结束。输出格式对于每个迷宫输出迷宫名称然后输出路径每行最多101010个坐标缩进两个空格或No Solution Possible。所有输出行除名称外均缩进两个空格。样例输入SAMPLE 3 1 N 3 3 1 1 WL NR * 1 2 WLF NR ER * 1 3 NL ER * 2 1 SL WR NF * 2 2 SL WF ELF * 2 3 SFR EL * 0 NOSOLUTION 3 1 N 3 2 1 1 WL NR * 1 2 NL ER * 2 1 SL WR NFR * 2 2 SR EL * 0 END样例输出SAMPLE (3,1) (2,1) (1,1) (1,2) (2,2) (2,3) (1,3) (1,2) (1,1) (2,1) (2,2) (1,2) (1,3) (2,3) (3,3) NOSOLUTION No Solution Possible题目分析迷宫尺寸小9×99 \times 99×9但状态包含位置和进入方向共81×432481 \times 4 32481×4324个状态。每个状态允许转移至最多333个相邻状态左、前、右。使用广度优先搜索BFS\texttt{BFS}BFS从起点状态开始直到到达终点状态即可找到最短路径。路径需要按格式输出。解题思路实现步骤确定如下步骤1\texttt{1}1. 读入迷宫名称若不是END则继续。读入起点坐标、起始方向、终点坐标。步骤2\texttt{2}2. 构建状态转移表。对于每个交叉口(r,c)(r,c)(r,c)读入多个方向组直到遇到*。每个方向组由进入方向ddd和后续转向字符组成。对于每个转向字符tttL、F、R计算从进入方向ddd转向后的新方向d′dd′以及对应相邻格子的坐标(nr,nc)(nr, nc)(nr,nc)。记录状态(r,c,d)(r,c,d)(r,c,d)可以转移到(nr,nc,d′)(nr, nc, d)(nr,nc,d′)。步骤3\texttt{3}3. 执行BFS\texttt{BFS}BFS。初始状态为起点移动一步后的状态即从起点按起始方向前进后的位置和方向。将起点本身作为路径的第一个节点。若起点即为终点但初始状态可能不是终点题目要求从起点出发按起始方向移动因此路径至少包含起点和下一个点。步骤4\texttt{4}4. 在BFS\texttt{BFS}BFS中记录每个状态的父状态以便回溯路径或直接在状态中携带路径向量。由于状态数少可直接在BFS\texttt{BFS}BFS队列节点中存储完整路径。步骤5\texttt{5}5. 当弹出节点位置为终点时输出路径。路径每101010个坐标换行每个坐标格式为(r,c)坐标间用空格分隔。输出缩进两个空格。步骤6\texttt{6}6. 若BFS\texttt{BFS}BFS队列为空则无解输出No Solution Possible。注意方向映射N对应行减111E对应列加111S对应行加111W对应列减111。转向计算需根据当前方向和转向类型确定新方向。代码实现// Abbotts Revenge// UVa ID: 816// Verdict: Accepted// Submission Date: 2016-12-13// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;mapchar,intdirection{{N,0},{E,1},{S,2},{W,3}};mapchar,intturn{{L,0},{F,1},{R,2}};structpackage{intr,c,d;vectorpairint,intwalk;};boolflagfalse;charstartd;string maze,sign;intstartr,startc,endr,endc,somer,somec;intvisited[10][10][4],successor[10][10][4][4],record[1000][2];intfwd[4][2]{{-1,0},{0,1},{1,0},{0,-1}};intoffset[4][3][3]{{{0,-1,3},{-1,0,0},{0,1,1}},{{-1,0,0},{0,1,1},{1,0,2}},{{0,1,1},{1,0,2},{0,-1,3}},{{1,0,2},{0,-1,3},{-1,0,0}}};boolbfs(){vectorpairint,intstartwalk{{startr,startc}};startrfwd[direction[startd]][0],startcfwd[direction[startd]][1];package start(package){startr,startc,direction[startd],startwalk};memset(visited,0,sizeof(visited));queuepackageunvisited;unvisited.push(start);while(unvisited.empty()false){package currentunvisited.front();unvisited.pop();intrcurrent.r,ccurrent.c,dcurrent.d;current.walk.push_back(make_pair(r,c));if(rendrcendc){for(inti0;icurrent.walk.size();i){if(i%100)cout ;cout (current.walk[i].first,current.walk[i].second);if((i1)%100)cout\n;}if(current.walk.size()%10!0)cout\n;returntrue;}visited[r][c][d]1;for(inti0;i3;i)if(successor[r][c][d][i]){intnextrroffset[d][i][0],nextccoffset[d][i][1],nextdoffset[d][i][2];if(visited[nextr][nextc][nextd]0)unvisited.push((package){nextr,nextc,nextd,current.walk});}}returnfalse;}intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);while(cinmaze,maze!END){memset(successor,0,sizeof(successor));cinstartrstartcstartdendrendc;while(cinsomer,somer0){cinsomec;while(cinsign,sign!*){for(inti1;isign.length();i)successor[somer][somec][direction[sign.front()]][turn[sign[i]]]1;}}coutmaze\n;if(!bfs())cout No Solution Possible\n;}return0;}总结本题通过广度优先搜索在状态空间位置 方向中求解最短路径状态数有限。关键在于正确解析输入建立状态转移表并处理初始状态起点移动一步后。输出格式要求每101010个坐标换行缩进两个空格。该解法时间复杂度O(V)O(V)O(V)空间O(V)O(V)O(V)其中VVV为状态数完全可行。注意输入中每个交叉口可能有多个方向组需全部读入。