UVA816 Abbott的复仇 Abbott's Revenge（final的BFS）（真•答案）

题目

写这道题差点没把我气死，网上的好多题解看了半天结果是假的…

题目PDF

【分析】

利用队列实现广度搜索BFS来遍历图寻找最短路径。

用一个三元组(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树中的父结点。

在输入过程中，读取r0,c0,dir，并且计算出r1,c1即初始状态位置，读取终点位置r2,c2。读取交叉点的位置允许出去的方向，将朝向 dir 和转弯方向 turn 转化为编号0_3和02，并储存在has_edge数组中，其中has_edge[r][c][dir][turn]表示当前状态是(r, c, dir)，是否可以沿着转弯方向turn行走。在BFS遍历的过程中，可以依据has_edge[r][c][dir][turn]判断位置(r, c, dir)是否可以这样转弯走到新状态。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e3+7;
const ll mod=2147483647;
struct node
{
    int x,y,dir;// 站在(r,c)，面朝方向dir(0~3分别表示N, E, S, W)
    /*node(int x=0,int y=0,int dir=0) { this->x=x; this->y=y; this->dir=dir; }*/
    node(int x=0, int y=0, int dir=0):x(x),y(y),dir(dir) {}
}father[10][10][4];//father[r][c][dir]表示了(r,c,dir)在BFS树中的父节点
int d[10][10][4];//用来累加起点到终点的距离
int has_edge[10][10][10][10];//保存每一个坐标的具体转向方式
const char* dirs="NESW";// 顺时针旋转
const char* turns="FLR";
int dir_id(char c){return strchr(dirs,c)-dirs;}//返回c在dirs的位置
int turn_id(char c){return strchr(turns,c)-turns;}
int x_0,x_1,y_0,y_1,x2,y2,dir;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
node walk(const node &u,int turn)
{
    int dir=u.dir;
    if(turn==1)dir=(dir+3)%4;//顺时针，表示左转
    if(turn==2)dir=(dir+1)%4;//逆时针，表示右转
    return node(u.x+dx[dir],u.y+dy[dir],dir);
}
//判断坐标是否出界
bool check(int x,int y)
{
    return x>=1&&x<=9&&y>=1&&y<=9;
}
bool read_case()
{
    char s1[100],s2[100];
    //s1是指当前的流程，x0表示起始行，y0表示起始列，s2起始方向，x2表示目标行，y2表示目标列
    if(scanf("%s%d%d%s%d%d",s1,&x_0,&y_0,s2,&x2,&y2)!=6)return false;
    printf("%s\n",s1);
    dir=dir_id(s2[0]);//方向在字符串dirs中的位置
    x_1=x_0+dx[dir];//第一步之后的行坐标
    y_1=y_0+dy[dir];//第二步之后的列坐标
    memset(has_edge,0,sizeof has_edge);
    for(;;)
    {
        int x,y;
        scanf("%d",&x);
        if(x==0)break;
        scanf("%d",&y);
        while(scanf("%s",s1)==1&&s1[0]!='*')
        {
            for(int i=1;i<=strlen(s1);++i)
                has_edge[x][y][dir_id(s1[0])][turn_id(s1[i])]=1;
        }
    }
    return true;
}
void print_ans(node u)
{ // 从目标结点逆序追溯到初始结点
    vector<node>nodes;
    for(;;)
    {
        nodes.push_back(u);
        if(d[u.x][u.y][u.dir]==0)break;//说明找到了终点
        u=father[u.x][u.y][u.dir];
    }
    nodes.push_back(node(x_0,y_0,dir));
    int cnt=0;
    for(int i=nodes.size()-1;i>=0;i--)
    {
        if(cnt%10==0)printf(" ");
        printf(" (%d,%d)", nodes[i].x, nodes[i].y);
        if((++cnt)%10==0)
            printf("\n");
    }
    if(nodes.size()%10!=0)printf("\n");
}
void solve()
{
    queue<node>q;
    memset(d,-1,sizeof d);
     //第一步之后，处于（2,1，N）的状态
    node u(x_1,y_1,dir);//走了一步之后的坐标
    d[u.x][u.y][u.dir]=0;
    q.push(u);
    while(!q.empty())
    {
        node u=q.front();
        q.pop();
        if(u.x==x2&&u.y==y2){print_ans(u);return ;}
        //判断当前坐标点，在当前转向的三个方向哪个是可以行使的？
        for(int i=0;i<3;i++)
        {
            node v=walk(u,i);
            //v是u坐标行走一步之后的坐标，走到终点没有初始化，has_edge值为0，不进入循环
            if(has_edge[u.x][u.y][u.dir][i]&&check(v.x, v.y)&&d[v.x][v.y][v.dir]<0)//能走且为出界且没走过
            {
                d[v.x][v.y][v.dir] = d[u.x][u.y][u.dir] +1;//累加1，最后得出起点到终点的距离
                father[v.x][v.y][v.dir]=u;//表示v的父节点是u
                q.push(v);
            }
        }
    }
    printf(" No Solution Possible\n");
}
int main()
{
    while(read_case())
    {
        solve();
    }
    return 0;
}