文章

14

粉丝

230

获赞

26

访问

71.1k

头像
t秒时间内可以到达的所有地方
P1126
发布于2022年8月10日 10:01
阅读数 4.3k

借助队列,用BFS方法

基本可以直接利用模板,需要修改跳出循环条件(step等于t)

当遍历到的结点有step等于t,说明,时间到,退出循环,打印输出数组

如果队列为空了,都没有结点的step等于t,说明,时间到时,毒早已入侵

另外,需要修改mpt数组。

带注释代码

#include<bits/stdc++.h>

using namespace std;
const int maxn = 100+5;
char mpt[maxn][maxn];
int vis[maxn][maxn];
int dir[4][2] = {0,1,1,0,0,-1,-1,0};
struct node
{
    int x,y;
    int step;
};
int bfs(int sx,int sy,int t)
{
    memset(vis,0,sizeof(vis));
    queue<node> q;
    q.push(node{sx,sy,0});
    vis[sx][sy]=1;
    mpt[sx][sy]='#';
    int ans=0;
    while(!q.empty())
    {

        node now = q.front();
        if(now.step==t)//判断条件
        {
            ans=1;
            break;
        }
        q.pop();
        for(int i=0; i<4; i++)
        {
            int x= now.x+dir[i][0];
            int y = now.y+dir[i][1];

            if(mpt[x][y]=='.'&&vis[x][y]==0)
            {
                q.push(node{x,y,now.step+1});
                vis[x][y]=1;
           ...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发