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

空·白 · 2019-09-20 21:23:32 · 题解

一题非常简单的广搜，尽管我一开始忘了无解的情况，但是这并不影响我AC（实际上还是有一些影响的）。

#include<bits/stdc++.h>
using namespace std;
int t=0,n,M;
int f[2010][2010];  //存地图；
int ans[2010][2010];    //存答案
int d[4][2]={{1,0},{0,1},{-1,0},{0,-1}};    //每次走的方向
queue<int > que;    //横坐标
queue<int > q;      //纵坐标
void bfs(int x,int y)
{
    int xx,yy;
    while(que.empty()==0)
    {   
        x=que.front();
        y=q.front();
        que.pop();
        q.pop();
        if(f[x][y]==2)      //判断找到了没有
        {
            cout<<ans[x][y];
            t=1;    //表示找到了
            break;
        }
        for(int i=0;i<4;i++)
        {
            xx=x+d[i][0];
            yy=y+d[i][1];
            if(f[xx][yy]!=1&&xx>=0&&xx<=n-1&&yy>=0&&yy<=M-1&&ans[xx][yy]==0)
            {
                que.push(xx);
                q.push(yy);
                if(f[x][y]==0)
                {
                    f[x][y]=1;
                }
                ans[xx][yy]=ans[x][y]+1;
            }
        }
    }
    if(t==0)    //无解
    {
        cout<<"No Way!";
    }
}
int main()
{
    int x,y;
    string s;
    cin>>n>>M;
    for(int i=0;i<=n-1;i++)
    {
        cin>>s;
        for(int j=0;j<=M-1;j++)     //初始化地图
        {
            if(s[j]=='.')
            {
                f[i][j]=0;
            }
            if(s[j]=='#')
            {
                f[i][j]=1;
            }
            if(s[j]=='d')
            {
                f[i][j]+=2;
            }
            if(s[j]=='m')
            {
                f[i][j]=1;
                x=i;
                y=j;
            }
        }
    }
    que.push(x);
    q.push(y);
    bfs(x,y);
}