疾跑冷喵
2022-01-21 12:21
采纳率: 60%
浏览 39

关于BFS搜索的问题

不管输入什么,都是输出NO,也不知道哪里有错误

img

#include<iostream>
#include<string.h>
#include<queue>
using namespace std;

const int maxn=1005;
char mpt[maxn][maxn];//存储地图
int dir[4][2]={{0,1},{0,-1},{-1,0},{1,0}};//代表方向
struct node
{
    int x,y;
};

bool bfs(int sx,int sy,int n,int m,int t)
{
    queue<node>q;
    q.push(node{sx,sy});
    while(t--)
    {
        int len=q.size();
        while(len--)
        {
            auto cur=q.front();//auto为自动判断数据类型
            q.pop();
            for(int i=0;i<4;i++)
            {
                int nx=cur.x+dir[i][0];
                int ny=cur.y+dir[i][1];
                if(nx >= 0 && nx < n && ny >= 0 && ny < m && mpt[nx][ny]=='.')
                {
                    mpt[nx][ny]='#';
                    q.push(node{nx,ny});
                }
            }
        }
        if(q.empty())  break;
    }
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            if(mpt[i][j]=='.')//找到了毒气还未扩散到的路径
                return true;
    if(t <= 0)  return true;
    else return false;
}

int main()
{
    int n,m,t;
    int sx,sy;
    while(cin>>n>>m>>t)
    {
        memset(mpt,'0',sizeof(mpt));//初始化
        for(int i=0;i<n;i++)  cin>>mpt[i];//输入地图
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(mpt[i][j]=='*');//找到初始位置
                {
                    mpt[i][j]='#';
                    sx=i,sy=j;
                }
            }
        }
      if(bfs(sx,sy,n,m,t))
        {
            for(int i=0;i<n;i++)
            {
                for(int j=0;j<m;j++)
                {
                    cout<<mpt[i][j];
                }
                cout<<endl;
            }
        }
      else  cout<<"NO"<<endl;
    }
    return 0;
}

1条回答 默认 最新

相关推荐 更多相似问题