[BFS]Abbott’s Revenge, World Finals 2000, Uva816

59 阅读 0 评论 39 点赞

我是靠谱客的博主冷酷泥猴桃，最近开发中收集的这篇文章主要介绍[BFS]Abbott’s Revenge, World Finals 2000, Uva816，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意：有一个最多包含9*9个节点的迷宫。输入起点、离开起点时的朝向和终点，求一条从起点到终点的最短路。
这个迷宫的特殊之处在于：进入一个交叉点的方向不同，允许从这个交叉点出去的方向也不同。例如1 2 WLF NR ER表示对于点(1,2)，当从W方向(即朝左)进入这个点时，只能向左拐或直行，从N方向和E方向进入这个点时只能向右拐。、

题解：本题与一般的迷宫问题的不同之处在于需要输出路径以及限制了行走方向，所以需要用到一个四元组(x,y,dir,pre)表示”位于(x,y)面朝dir前驱为pre”这个状态。假设起点为(x0,y0)，方向为dir，那么初始状态并不是(x0,y0,dir)，而是(x1,y1,dir)，其中(x1,y1)为从起点走一步之后的坐标。在BFS树中，用flag[x][y][dir][pos]表示能否在从dir方向进入点(x,y)时向pos行进，而用visit[x][y][dir][pos]标记这条路是否已被走过。
对于方向，使用map将四种方向与三种转弯方式分别对应0-3与0-2，使得我们可以根据当前状态和转弯方式直接计算出后继状态。而对于打印路径，可以利用状态中的前驱，递归地找出实际的路径。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<map>
#include<stack>
#include<vector>
#include<iostream>
#include<algorithm>
#define maxn 15
#define maxm 10050
#define INF 0x3f3f3f3f
#define eps 1e-8
const int mod=1e9+7;
using namespace std;
typedef long long ll;

bool maze[maxn][maxn];
bool flag[maxn][maxn][4][3];
bool visit[maxn][maxn][4][3];
int step[maxn][maxn][4];
int sx,sy,ex,ey,dx,dy,len,vis;
char st,di[8],name[25];
int dis[4][2]={0,-1,-1,0,0,1,1,0};
struct node
{
    int x,y;
    int dir;
    int pre;
}start,ss,s[maxm],q[maxm];
map<char,int>d;
node pa[maxn][maxn][4];

bool judge(int x,int y)
{
    if(x>=1&&y>=1&&x<=9&&y<=9)return true;
    return false;
}

void init()
{
    memset(maze,0,sizeof(maze));
    memset(flag,0,sizeof(flag));
    memset(step,0,sizeof(step));
    memset(visit,0,sizeof(visit));
    vis=len=0;
}

void print(int num)
{
    if(num==-1)return;
    print(q[num].pre);
    s[len++]=q[num];
}

void bfs()
{
    node now,next;
    int cnt=0,top=0;
    ss.x=sx,ss.y=sy;
    start.x=sx+dis[d[st]][0];
    start.y=sy+dis[d[st]][1];
    start.dir=ss.dir=d[st];
    start.pre=-1;
    pa[start.x][start.y][start.dir]=ss;
    step[sx][sy][d[st]]=0;
    step[start.x][start.y][start.dir]=1;
    q[top++]=start;
    visit[sx][sy][ss.dir][ss.dir]=1;
    while(cnt<top)
    {
        now=q[cnt++];
        if(now.x==ex&&now.y==ey)
        {
            vis=1;
            print(cnt-1);
            break;
        }
        int nx=now.x,ny=now.y;
        for(int i=0;i<3;i++)
        {
            if(flag[nx][ny][now.dir][i]&&!visit[nx][ny][now.dir][i]&&judge(nx,ny))
            {
                int u=(now.dir+i+3)%4;
                next.x=nx+dis[u][0];
                next.y=ny+dis[u][1];
                next.dir=u;
                next.pre=cnt-1;
                step[next.x][next.y][u]=step[nx][ny][now.dir]+1;
                visit[nx][ny][now.dir][i]=1;
                pa[next.x][next.y][u]=now;
                q[top++]=next;
            }
        }
    }
}

int main()
{
    while(scanf("%s",name))
    {
        if(!strcmp(name,"END"))
            break;
        init();
        scanf("%d%d",&sx,&sy);
        getchar(),scanf("%c",&st),getchar();
        scanf("%d%d",&ex,&ey);
        d['W']=0,d['N']=1,d['E']=2,d['S']=3;
        d['L']=-1,d['R']=1,d['F']=0;
        while(scanf("%d",&dx)&&dx!=0)
        {
            scanf("%d",&dy);
            while(scanf("%s",di))
            {
                if(di[0]=='*')
                    break;
                for(int i=1;i<strlen(di);i++)
                    flag[dx][dy][d[di[0]]][d[di[i]]+1]=1;
            }
        }
        printf("%sn",name);
        bfs();
        if(!vis)
            printf("  No Solution Possiblen");
        else
        {
            for(int i=len;i>=1;i--)
                s[i]=s[i-1];
            s[0]=ss;
            len++;
            int k=1;
            for(int i=0;i<len;i++)
            {
                if(k%10==1)
                    printf(" ");
                printf(" (%d,%d)",s[i].x,s[i].y);
                if(k%10==0)
                    printf("n");
                k++;
            }
            if(len%10!=0)
                printf("n");
        }
    }
    return 0;
}