题目内容

P1126

题面很长,大意就是控制一个机器人,但是这题最恶心的地方就是机器人的位置是点的坐标,但障碍物是格子

解题思路

这题调了我真的好久,是我见过最难调的搜索题之一,考验代码能力。从去年的 9 月份调了几个小时放弃之后直到今天再拿起此题,然后调半个小时过去了,其中两次 WA 一次是因为没判 -1,一次是因为判断边界的函数把 m 写成 n。

具体的思路就是,进行 bfs,每次转移的时候存储机器人左上角的坐标,判断障碍和越界的时候只需要判断他四个格子有没有障碍就可以了。然后就是一些 trick,比如采用 kln 和 kcol 数组来进行方便的向前移动的坐标转移,然后就是 vis 数组记得多开一维存储方向,再就是记得 x 和 y 分别代表的是行还是列,搞明白之后还是比较好写的。

查错真的是花了我不少时间,输出中间变量太香了,可以很方便的快速定位到错误的发生位置

然后这个狗东西其实也可以用双向搜索,但是我懒得用了,单向也可以过的

#include <cstdio>
#include <queue>
using namespace std;

int n,m;
//n is line, m is col
int sx,sy,fx,fy;//存起终点
int maze[52][52];//存迷宫
int kln[4][4],kcol[4][4];//第一维是朝向,第二维是要移动的步数
bool vis[52][52][4];//存储每个点的方向是否访问过

struct node
{
    int x,y;//机器人左上角坐标
    int face;//目前的朝向
    int step;//目前已经走的时间
    node(){}
    node(int _x,int _y,int _face,int _step)
    {
        x=_x;
        y=_y;
        face=_face;
        step=_step;
    }
};

queue<node> q;

void updk()//kln和kcol数组的初始化函数
{
    kln[1][1]=1,kln[1][2]=2,kln[1][3]=3;
    kln[3][1]=-1,kln[3][2]=-2,kln[3][3]=-3;
    kln[0][1]=kln[0][2]=kln[0][3]=0;
    kln[2][1]=kln[2][2]=kln[2][3]=0;
    kcol[1][1]=kcol[1][2]=kcol[1][3]=0;
    kcol[3][1]=kcol[3][2]=kcol[3][3]=0;
    kcol[0][1]=1,kcol[0][2]=2,kcol[0][3]=3;
    kcol[2][1]=-1,kcol[2][2]=-2,kcol[2][3]=-3;
    return;
}

inline bool isvalid(int x,int y)//判断一个机器人的位置是否合法
{
    if(x<1||x>n-1||y<1||y>m-1)//判边界,当时就是因为m写成n了WA第3个点
        return false;
    if(maze[x][y]||maze[x+1][y]||maze[x+1][y+1]||maze[x][y+1])//判障碍物
        return false;
    return true;
}

int bfs()
{
    int ans=0x3f3f3f3f;
    bool flag=0;
    while(!q.empty())
    {
        int nowx=q.front().x,nowy=q.front().y,nowdir=q.front().face,nowstep=q.front().step;
        q.pop();
        if(!isvalid(nowx,nowy))
            continue;
        if(nowx==fx && nowy==fy)
        {
            ans=nowstep<ans?nowstep:ans;
            flag=1;
        }
        if(!vis[nowx][nowy][(nowdir+1)%4])//这里是方向的处理,适当运用模运算可以简化思维
        {
            vis[nowx][nowy][(nowdir+1)%4]=1;//记得vis数组更新
            q.push(node(nowx,nowy,(nowdir+1)%4,nowstep+1));
        }
        if(!vis[nowx][nowy][(nowdir+3)%4])//一样的道理,换一个方向而已
        {
            vis[nowx][nowy][(nowdir+3)%4]=1;
            q.push(node(nowx,nowy,(nowdir+3)%4,nowstep+1));
        }
        for(int s=1;s<=3;s++)//枚举向前走的步数
        {
            int xx=nowx+kln[nowdir][s],yy=nowy+kcol[nowdir][s];
            if(!isvalid(xx,yy))//如果发现走1步不行就要及时break,否则WA
                break;
            if(!vis[xx][yy][nowdir])//如果没有重就加入队列
            {
                vis[xx][yy][nowdir]=1;
                q.push(node(xx,yy,nowdir,nowstep+1));
            }
        }
    }
    return flag?ans:-1;
}

int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&maze[i][j]);
    updk();
    char dir;
    scanf("%d %d %d %d %c",&sx,&sy,&fx,&fy,&dir);
    if(dir=='E') dir=0;
    if(dir=='S') dir=1;
    if(dir=='W') dir=2;
    if(dir=='N') dir=3;
    vis[sx][sy][dir]=1;
    q.push(node(sx,sy,dir,0));
    printf("%d\n",bfs());
    return 0;
}

这题细节还是很多的,可以锻炼代码能力和调试能力。

最后修改日期: 2020年3月3日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。