题解 P2298 【Mzc和男家丁的游戏】

· · 题解

既然没有人打手写队列,那我就来水一波手写队列.

不多BB 直接干货带注释

#include<bits/stdc++.h>
using namespace std ;

int n,m;
char ll[2006][2006];
int a[2006][2006];
int u[4]={0,-1,0,1};
int v[4]={-1,0,1,0};
int walk[2006][2006];
int que[4000006][3];

inline int read()//读优不解释
{
    register int res=0,flag=1;
    register char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')
        {
            flag=-1;
        }
        ch=getchar();
    }
    while(isdigit(ch))
    {
        res=(res<<3)+(res<<1)+(ch^48);
        ch=getchar();
    }
    return flag*res;
}

inline void bfs(register int x,register int y)
{
    register int head=0,tail=1;
    que[tail][0]=x;
    que[tail][1]=y;
    que[tail][2]=0;//在传统广搜手写队列基础上开一个第三项,记录步数
    walk[x][y]=1;
    do
    {
        head++;
        register int dx=que[head][0];
        register int dy=que[head][1];
        register int step=que[head][2];//步数与坐标一起进行处理
        for(register int i=0;i<=3;++i)
        {
            register int uu=dx+u[i];
            register int vv=dy+v[i];
            if(walk[uu][vv]==0&&uu<=n&&uu>0&&vv<=m&&vv>0)
            {
                walk[uu][vv]=1;
                tail++;
                que[tail][0]=uu;
                que[tail][1]=vv;
                que[tail][2]=step+1;//更新步数
                if(a[uu][vv]==1)
                {
                    printf("%d\n",step+1);//注意要加1
                    return ;
                }
            }
        }
    }while(head<tail);
    printf("No Way!\n");
    return ;
}

int main()
{
    register int x,y;
    n=read();
    m=read();
    for(register int i=1;i<=n;++i)
    {
        for(register int j=1;j<=m;++j)
        {
            cin>>ll[i][j];
            if(ll[i][j]=='m')
            {
                x=i;
                y=j;
            }
            if(ll[i][j]=='#')
            {
                walk[i][j]=1;
            }
            if(ll[i][j]=='d')
            {
                a[i][j]=1;
            }
        }
    }

    bfs(x,y);

    return 0;
}