紫书第六章-----数据结构基础（BFS求最短路）

74 阅读 0 评论 49 点赞

我是靠谱客的博主机灵绿茶，最近开发中收集的这篇文章主要介绍紫书第六章-----数据结构基础（BFS求最短路），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

特别说明：本文章参考刘汝佳《算法竞赛入门经典》（第2版）

很多复杂的迷宫问题都可以转化为最短路径问题，然后用BFS求解。在套用BFS框架之前，需要先搞清楚图中的“结点”包含哪些内容。

【例题6-14 Abbott’s Revenge UVA - 816】
【分析】
本题整体是使用用BFS解决最短路的问题。在一般的图中，一个结点就是一个结点，访问后可以标记为1，但本题的图中，一个结点可能是当做多个结点用的，因为这个结点有自己的方向，加上方向这个维度，可以从各个方向访问这个结点，从一个方向访问过这个结点后，只能把对应的这个方向的这个结点标记为1。其他细节直接看代码注释。

【代码如下】

#include<iostream>
#include<queue>
#include<cstring>
#include<vector>
#include<cstdio>
#include<string>
using namespace std;

char name[25];//迷宫的名字，注意这里不能用char *name，这样是不能直接用cin>>name的
char *dirs="NESW";//结点方向
char *turns="FLR";//结点转弯方向
int l[4]={3,0,1,2};//各个方向左转弯后的方向
int r[4]={1,2,3,0};//各个方向右转弯后的方向
int dr[4]={-1,0,1,0};//转向各个方向后横坐标变化幅度
int dc[4]={0,1,0,-1};//转向各个方向后纵坐标的变化幅度

//定义结点，包含结点的行r，列c，方向dir
struct node{
    int r,c,dir;
    //发现下面构造函数中的变量要有初值，不然会报错
    node(int r=0,int c=0,int dir=0):r(r),c(c),dir(dir){}
};

int r0,c0,dir;//起始结点信息
int r1,c1;//起始结点下一个结点信息
int r2,c2;//目标结点信息
bool vis[10][10][4];//标记结点是否被访问过
bool has_edge[10][10][4][3];//表示结点r,c,dir是否可以沿着某转弯方向走
node par[10][10][4];//某结点的父母结点，用来记录、打印路径


void print_ans(node u){
    vector<node>nodes;
    while(1){
        nodes.push_back(u);
        if(!vis[u.r][u.c][u.dir]) break;//注意这里是先把u进入nodes，再判断vis。
    //要注意vis[r1][c1][dir]=0，到该结点后，先把它进入nodes，再判断vis，再结束
        u=par[u.r][u.c][u.dir];
    }
    nodes.push_back(node(r0,c0,dir));//再把r0,c0,dir这个结点进入nodes

    int cnt=0;
    for(int i=nodes.size()-1;i>=0;i--){
        if(cnt%10==0) cout<<" ";
        cout<<" ("<<nodes[i].r<<","<<nodes[i].c<<")";
        if(++cnt%10==0) cout<<endl;
    }
    if(nodes.size()%10!=0) cout<<endl;
}

//判断某结点能否沿着某转弯方向走
node walk(node v,int turn){
    int dir=v.dir;
    if(turn==1) dir=l[dir];
    else if(turn==2) dir=r[dir];
    return node(v.r+dr[dir],v.c+dc[dir],dir);
}

//判断某结点是否超出了图的范围
bool inside(int r,int c){
    return (r>=1 && r<=9 && c>=1 && c<=9);
}
//找到某方向在dirs中所对应的下标
int dir_id(char c){
    return strchr(dirs,c)-dirs;
}
//找到某转向在turns中所对应的下标
int turn_id(char c){
    return strchr(turns,c)-turns;
}

void read_input(){
    char ch;
    cin>>r0>>c0>>ch;
    dir=dir_id(ch);
    r1=r0+dr[dir];c1=c0+dc[dir];
    cin>>r2>>c2;
    memset(has_edge,0,sizeof(has_edge));
    int i,j;
    while(cin>>i){
        if(i==0) break;
        cin>>j;
        string s;
        while(cin>>s){
            if(s[0]=='*') break;
            int dirc=dir_id(s[0]);
            for(int k=1;k<s.length();k++){
                int turn=turn_id(s[k]);
                has_edge[i][j][dirc][turn]=1;
            }
        }
    }
}

void bfs(){
    memset(vis,0,sizeof(vis));
    queue<node>que;
    node u(r1,c1,dir);
    que.push(u);//注意此时没有把vis[r1][c1][dir]标记为1，这是为了打印路径的时候方便在此结点处结束
    while(!que.empty()){
        node v=que.front();que.pop();
        if(v.r==r2 && v.c==c2){print_ans(v);return;}
        for(int i=0;i<3;i++){
            node w=walk(v,i);
            if(has_edge[v.r][v.c][v.dir][i] && !vis[w.r][w.c][w.dir] && inside(w.r,w.c)){
                que.push(w);
                vis[w.r][w.c][w.dir]=1;
                par[w.r][w.c][w.dir]=v;//记录路径
            }
        }
    }
    cout<<"  No Solution Possible"<<endl;
}

int main()
{
    while(cin>>name){
        if(strcmp(name,"END")==0) break;
        cout<<name<<endl;
        read_input();
        bfs();
    }
    return 0;
}