TYVJ 1117 BFS

无限ＷＡ。。参考了一下题解和同学写的。。。。。。。

可以在bfs的基础上改一下。。

读入的时候平地权值是2 草地是0

bfs的时候如果搜到的是平地，那么直接加入，如果搜到的是草地，那么记录是草地。

从队列里面拿出来的时候，如果是平地就直接那出来，如果是草地就加到队尾，标记成平地。

目的就是保证层数和时间同步！start和end就看成平地好了

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <queue>

#include <iostream>

using namespace std;

int x,y,t,a[66][66],sx,sy,ex,ey,vis[66][66];

int xx[]={1,-1,0,0},yy[]={0,0,1,-1};

queue <int> s,e;

int bfs()

{

    s.push(sx);e.push(sy);

    while(!s.empty())

    {

        int tempa=s.front(),tempb=e.front();

        s.pop();e.pop();

        if(tempa==ex&&tempb==ey) return vis[tempa][tempb];

        if(a[tempa][tempb]==1)//草地加入

        {

            s.push(tempa);e.push(tempb);

            a[tempa][tempb]=2;//标记成平地

            vis[tempa][tempb]+=1;

            continue;

        }

        for(int i=0;i<=3;i++)

        {

            int dx=tempa+xx[i],dy=tempb+yy[i];

            if(dx<=x&&dx>0&&dy<=y&&dy>0&&a[dx][dy]!=-1&&!vis[dx][dy])

            {

                if(a[dx][dy]==0)  a[dx][dy]=1;

                s.push(dx);e.push(dy);

                vis[dx][dy]=vis[tempa][tempb]+1;

            }

        }

    }

}

int main()

{

    scanf("%d%d%d",&t,&y,&x);//读入又是反的

    char cc;

    for(int i=1;i<=x;i++)

    {

        for(int j=1;j<=y;j++)

        {

            cin>>cc;

            if(cc=='#')     a[i][j]=0;

            else if(cc=='.')a[i][j]=2;

            else if(cc=='o')a[i][j]=-1;

            else if(cc=='s')

            {

                sx=i;sy=j;a[i][j]=2;

            }

            else if(cc=='m')

            {

                ex=i;ey=j;a[i][j]=2;

            }

        }

    }

    int k=bfs();

    k<t?printf("%d",k):printf("55555");//当k=t，则判断为未到！！因为这个WA了两次。。。

}