专栏首页用户6093955的专栏Fire! UVA - 11624 (两步bfs)

Fire! UVA - 11624 (两步bfs)

题目链接

题意

人要从迷宫走出去,火会向四个方向同时扩散

分析

两步bfs,先出火到达各地时的时间(设初始时间为0,人每走一步为1s,在着一步内火可以向四周可触及的方向同时扩散),然后在bfs人,人能在某地当且仅当所到时间小于火到达时间

代码

#include<iostream>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn = 1000+10;
const int INF = 0x3f3f3f3f;
int R, C, tcases;
int begx, begy;
char maze[maxn][maxn];
int fire_time[maxn][maxn];
int per_time[maxn][maxn];
int vis[maxn][maxn];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
typedef pair<int, int> P;
queue<P> pos;
bool op(int a, int b)
{
    if(a >= 0 && a < R && b >= 0 && b < C)
        return true;
    return false;
}
void init()
{
    while(!pos.empty())
        pos.pop();
    memset(vis, 0, sizeof(vis));
    bool is_fire = false;       //看是否有火
    for(int i = 0; i < R; i++)
    {
        for(int j = 0; j < C; j++)
        {
            per_time[i][j] = INF;
            fire_time[i][j] = INF;
            if(maze[i][j] == 'J')
            {
                begx = i;
                begy = j;
                per_time[i][j] = 0;
            }
            if(maze[i][j] == 'F')
            {
                fire_time[i][j] = 0;
                vis[i][j] = 1;
                is_fire = true;
                pos.push(P(i, j));      //将初始时F的位置插入到队列中
            }
        }
    }
    if(!is_fire)
        return ;

    while(!pos.empty())
    {
        P p = pos.front();
        pos.pop();  //该点周围已遍历,故删掉
        for(int i = 0; i < 4; i++)
        {
            int curx = p.first + dx[i], cury = p.second + dy[i];
            if(op(curx, cury) && !vis[curx][cury] && maze[curx][cury] != '#')
            {
                vis[curx][cury] = 1;
                fire_time[curx][cury] = fire_time[p.first][p.second] + 1;
                pos.push(P(curx, cury));
            }
        }
    }
}
int bfs()
{
    while(!pos.empty())
        pos.pop();
    memset(vis, 0, sizeof(vis));
    pos.push(P(begx, begy));    //把J的初始位置插入
    vis[begx][begy] = 1;
    while(!pos.empty())
    {
        P p = pos.front();
        pos.pop();
        for(int i = 0; i < 4; i++)
        {
            int curx = p.first + dx[i], cury = p.second + dy[i];
            if(!op(curx, cury))
                return per_time[p.first][p.second] + 1;
            if(!vis[curx][cury] && maze[curx][cury] == '.' && per_time[p.first][p.second] + 1 < fire_time[curx][cury])   //人先fire一步到达
            {
                vis[curx][cury] = 1;
                pos.push(P(curx, cury));
                per_time[curx][cury] = per_time[p.first][p.second] + 1;
            }
        }
    }
    return INF;

}
int main()
{
    cin >> tcases;
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    while(tcases--)
    {
        cin >> R >> C;
        for(int i = 0; i < R; i++)
            scanf("%s", maze[i]);
        init(); //探寻F到达各个点时的时间,用bfs
        int ans = bfs();
        if(ans != INF)
            cout << ans << endl;
        else
            cout << "IMPOSSIBLE" << endl;
    }
}

注意:一般 freopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);这两句不要出现在代码里。

memset不要想当然的认为它可以对int数组赋任意值,实际上它只对-1,0有效,原因见https://blog.csdn.net/lyj2014211626/article/details/65481630https://blog.csdn.net/ko_tin/article/details/52947059

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【软件18-循环队列及综合】

    F:将向量空间想象为一个首尾相接的圆环,并称这种向量为循环向量。存储在其中的队列称为循环队列(Circular Queue)。这种循环队列可以以单链表的方式来在...

    _DIY
  • 走迷宫(bfs, 最短路)

    _DIY
  • Problem E: 数量的类模板

    _DIY
  • SNMP学习笔记之Python的netsnmp和pysnmp的性能对比

    用python获取snmp信息有多个现成的库可以使用,其中比较常用的是netsnmp和pysnmp两个库。网上有较多的关于两个库的例子。

    Jetpropelledsnake21
  • JavaScript 技术篇-chrome浏览器读取剪切板命令document.execCommand(‘paste‘)返回false原因及解决方法

    新版本 chrome 执行 document.execCommand('paste') 返回 false 因为读取剪切板涉及用户隐私安全,必须的用户允许的情况下...

    小蓝枣
  • 漫画:滑动窗口系列 第三讲(找到字符串中所有字母异位词)

    第438题:给定一个字符串 s 和一个非空字符串 p,找到 s 中所有是 p 的字母异位词的子串,返回这些子串的起始索引。

    程序员小浩
  • 用于将机器学习模型部署为生产Web服务的开源平台:Cortex

    如果正在寻找一种将机器学习模型部署为生产Web服务的工具,那么 “ Cortex” 可能是一个不错的选择。这个开源平台是使用AWS SageMaker服务模型...

    代码医生工作室
  • Oracle 触发器中修改字段值

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1148526
  • Docker和k8s的故障排除和监控利器 Weave-Scope服务

    Weave-Scope服务是一个用来监控docker容器、k8s等(包括宿主机)的资源使用状况的,从根本上来说,有些类似于Zabbix等监控服务,该服务式基于容...

    小手冰凉
  • 分析Oracle在云上实现高可用的几种实现方式

    针对Oracle迁移上云项目,云提供给用户的物理机上加载有三张网卡供用户使用,一张用于跑业务,另外两张可以用于心跳线网络。另外,存储网络是单独的网口,在建设时已...

    希望的田野

扫码关注云+社区

领取腾讯云代金券