欢迎访问我的Uva题解目录哦 https://blog.****.net/richenyunqi/article/details/81149109

题目描述

题意解析

有一个最多包含9*9个交叉点的迷宫。输入起点、离开起点时的朝向和终点，求一条最短路（多解时任意输出一个即可）。
以题目中的Figure 1为例，这个迷宫的特殊之处在于：进入一个交叉点的方向（用NEWS这4个字母分别表示北东西南，即上右左下）不同，允许出去的方向也不同。例如，1 2 WLF NR ER 表示交叉点(1,2)（上数第1行，左数第2列）有3个路标（字符“*”只是结束标志），如果进入该交叉点时的朝向为W（即朝左），则可以左转（L）或者直行（F）；如果进入时朝向为N或者E则只能右转（R）。注意：初始状态是“刚刚离开入口”，所以即使出口和入口重合，最短路也不为空。例如，图6-14中的一条最短路为(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)。

算法设计

参考《算法竞赛入门经典（第2版）》中的分析：

本题和普通的迷宫在本质上是一样的，但是由于“朝向”也起到了关键作用，所以需要用一个三元组(r, c, dir)表示“位于(r,c)，面朝dir”这个状态。假设入口位置为(r0, c0)，朝向为dir，则初始状态并不是(r0, c0, dir)，而是(r1, c1, dir)，其中，(r1,c1)是(r0,c0)沿着方向dir走一步之后的坐标。此处用d[r][c][dir]表示初始状态到(r,c,dir)的最短路长度，并且用p[r][c][dir]保存了状态(r,c,dir)在BFS树中的父结点。
提示6-22：很多复杂的迷宫问题都可以转化为最短路问题，然后用BFS求解。在套用BFS框架之前，需要先搞清楚图中的“结点”包含哪些内容。
提示6-23：使用BFS求出图的最短路之后，可以用递归方式打印最短路的具体路径。如果最短路非常长，递归可能会引起栈溢出，此时可以改用循环，用vector保存路径。

我的算法的主要思想与书中类似，代码中添加了足够的注释，读者直接浏览我的代码即可。

C++代码

#include<bits/stdc++.h>
using namespace std;
struct Node{//结点类
    int r,c,d;//行、列、方向
    Node(int row=0,int col=0,int direc=0):r(row),c(col),d(direc){}
};
int direction[4][2]={{-1,0},{0,1},{1,0},{0,-1}};//NESW方向
unordered_map<char,int>trans={{'N',0},{'E',1},{'S',2},{'W',3},{'L',-1},{'R',1},{'F',0}};//字符与方向的映射
Node start,dest,past[10][10][4];//起点、终点、每个结点在最短路径中的父节点
vector<int>point[10][10][4];//每个结点处的路标及朝向
bool BFS(Node p){//广度优先搜索求最短路
    queue<Node>q;
    q.push(p);//入队
    bool inQueue[10][10][4]={false};//某结点是否已经进入队列
    inQueue[p.r][p.c][p.d]=true;//该结点已进入队列
    past[p.r][p.c][p.d]=start;//置父节点
    while(!q.empty()){//队列不空
        p=q.front();//出队
        q.pop();
        if(p.r==dest.r&&p.c==dest.c){//到达终点
            dest.d=p.d;//补充终点的朝向
            return true;//找到了最短路，返回true
        }
        if(p.r>0&&p.r<10&&p.c>0&&p.c<10&&!point[p.r][p.c][p.d].empty()){//观察该结点是否有该朝向的路标
            for(int i:point[p.r][p.c][p.d]){//遍历该路标下的转向
                int d=(p.d+i+4)%4,ii=p.r+direction[d][0],jj=p.c+direction[d][1];//求转向之后下一个节点
                if(ii>0&&ii<10&&jj>0&&jj<10&&!inQueue[ii][jj][d]){//下一个节点尚未入队
                    q.push(Node(ii,jj,d));//入队
                    inQueue[ii][jj][d]=true;//该结点已进入队列
                    past[ii][jj][d]=p;//置父节点
                }
            }
        }
    }
    return false;//找不到最短路，返回false
}
void DFS(Node v,vector<Node>&path){//深度优先搜索打印最短路径
    if(v.r==start.r&&v.c==start.c&&v.d==start.d){//到达了起点
        path.push_back(v);
        for(int i=0;i<path.size();++i)//打印
            printf("%s (%d,%d)",i%10==0?"\n ":"",path[path.size()-1-i].r,path[path.size()-1-i].c);
        puts("");
        return;
    }
    path.push_back(v);
    DFS(past[v.r][v.c][v.d],path);//深度优先搜索父节点
}
int main(){
    string s;
    while(getline(cin,s)&&s!="END"){
        for(int i=0;i<10;++i)
            for(int j=0;j<10;++j)
                for(int k=0;k<4;++k){
                    past[i][j][k]=Node();
                    point[i][j][k].clear();
                }
        printf("%s",s.c_str());
        cin>>start.r>>start.c>>s>>dest.r>>dest.c;
        start.d=-1;//到达起点时的朝向置为-1
        int a,b,d=trans[s[0]];
        while(scanf("%d%*c",&a)&&a!=0){
            scanf("%d",&b);
            while(cin>>s&&s!="*"){
                for(int j=1;j<s.size();++j)
                    point[a][b][trans[s[0]]].push_back(trans[s[j]]);
            }
        }
        if(BFS(Node(start.r+direction[d][0],start.c+direction[d][1],d))){//直接从起点的下一个节点开始搜索
            vector<Node>path;
            DFS(dest,path);
        }else
            puts("\n  No Solution Possible");
    }
    return 0;
}