首页 > 其他分享 >10.起火迷宫

10.起火迷宫

时间:2023-04-02 20:33:35浏览次数:40  
标签:10 int 迷宫 起火 dist1 st1 st2 dist2 push

原题链接:acwing.com/problem/content/submission/4227/

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;

typedef pair<int,int> PII;
#define x first
#define y second
const int N=1010;
int n,m;
char g[N][N];
PII st2;
vector<PII> nums;
int dist1[N][N],dist2[N][N];
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
int ans;

void bfs1()
{
    queue<PII> q;
    memset(dist1,0x3f,sizeof dist1);
    for(auto st1:nums)
    {
        q.push(st1);
        dist1[st1.x][st1.y]=0;
    }
    while(q.size())
    {
        auto t=q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {
            int x=dx[i]+t.x,y=dy[i]+t.y;
            if(x<0||x>=n||y<0||y>=m||g[x][y]!='.') continue;
            if(dist1[x][y]==0x3f3f3f3f){
                dist1[x][y]=dist1[t.x][t.y]+1;
                q.push({x,y});
            }
        }
    }
}

int bfs2()
{
    queue<PII> q;
    q.push(st2);
    memset(dist2,0x3f,sizeof dist2);
    dist2[st2.x][st2.y]=0;
    while(q.size())
    {
        auto t=q.front();
        q.pop();
        if(t.x==0||t.x==n-1||t.y==0||t.y==m-1){
            if(dist2[t.x][t.y]+1<=dist1[t.x][t.y])
                return dist2[t.x][t.y]+1;
        }
        for(int i=0;i<4;i++)
        {
            int x=dx[i]+t.x,y=dy[i]+t.y;
            if(x<0||x>=n||y<0||y>=m||g[x][y]!='.') continue;
            if(dist2[x][y]==0x3f3f3f3f){
                if(dist2[t.x][t.y]+1>=dist1[x][y]) continue;
                dist2[x][y]=dist2[t.x][t.y]+1;
                q.push({x,y});
            }
        }
    }
    return -1;
}

int main()
{
    int tt;
    cin>>tt;
    while(tt--)
    {
        scanf("%d%d",&n,&m);
        nums.clear();
        ans=0x3f3f3f3f;
        for(int i=0;i<n;i++)
            scanf("%s",g[i]);
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
            {
                if(g[i][j]=='F') nums.push_back({i,j});
                else if(g[i][j]=='J') st2={i,j};
            }
        bfs1();
        int t=bfs2();
        if(t==-1) puts("IMPOSSIBLE");
        else printf("%d\n",t);
    }
    return 0;
}

标签:10,int,迷宫,起火,dist1,st1,st2,dist2,push
From: https://www.cnblogs.com/linearlearn/p/17281283.html

相关文章

  • 【Pandas数据处理100例目录】Python数据分析玩转Excel表格数据
    前言大家好,我是阿光。本专栏整理了《Pandas数据分析处理》,内包含了各种常见的数据处理,以及Pandas内置函数的使用方法,帮助我们快速便捷的处理表格数据。正在更新中~✨......
  • 2024届计算机秋招100天备战:力扣每日打卡挑战全记录 & 面试题总结
    最近两个月力扣困难题不再落下,打卡全满勤,激发了持续刷题的斗志。这里将持续记录打卡过程中的难题和面试八股。2023/4/21039.多边形三角剖分的最低得分题目大意:多边形每个节点有一个数值,将多边形三角剖分,得分为所有三角形节点乘积之和。求三角剖分后的最低得分。做题评价:虽......
  • 102.二叉树的层序遍历
    给你一个二叉树,请你返回其按层序遍历得到的节点值。(即逐层地,从左到右访问所有节点)classTreeNode{public:intval;TreeNode*left;TreeNode*right;TreeNode():val(NULL),left(nullptr),right(nullptr){}TreeNode(intx):val(x),left(nullptr),rig......
  • PAT Basic 1064. 朋友数
    PATBasic1064.朋友数1.题目描述:如果两个整数各位数字的和是一样的,则被称为是“朋友数”,而那个公共的和就是它们的“朋友证号”。例如123和51就是朋友数,因为1+2+3=5+1=6,而6就是它们的朋友证号。给定一些整数,要求你统计一下它们中有多少个不同的朋友证号。2.输入......
  • 利民(Thermalright)HR-10 2280 固态硬盘SSD散热器 - 我的硬件配置
    ......
  • PAT Basic 1063. 计算谱半径
    PATBasic1063.计算谱半径1.题目描述:在数学中,矩阵的“谱半径”是指其特征值的模集合的上确界。换言之,对于给定的\(n\)个复数空间的特征值\({a_1+b_1i,⋯,a_n+b_ni}\),它们的模为实部与虚部的平方和的开方,而“谱半径”就是最大模。现在给定一些复数空间的特征值,请你计算......
  • Security Onion Solutions 2.3.10部署指南
    https://blog.csdn.net/lcgweb/article/details/109983444?spm=1001.2101.3001.6650.16&utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7EESLANDING%7Edefault-16-109983444-blog-83414776.235%5Ev27%5Epc_relevant_landingrelevant&depth_1-utm_sou......
  • Java实现新建三个线程,每个线程顺序打印5个数字,打印到100
    方法一:synchronized+wait+notify//三个线程循环打印数字,每个打印5个,打印数字到numclassWaitNotifyABC{  privatevolatileintnum=0;//线程共享变量  /**Object和this都可以对同步代码块加锁,但是this锁的是类的实例,如果该实例被他人拿走,  则本线......
  • AcWing 1013. 机器分配
    总公司拥有 M 台 相同 的高效设备,准备分给下属的 N 个分公司。各分公司若获得这些设备,可以为国家提供一定的盈利。盈利与分配的设备数量有关。问:如何分配这M台设备才能使国家得到的盈利最大?求出最大盈利值。分配原则:每个公司有权获得任意数目的设备,但总台数不超过设备数......
  • PAT Basic 1062. 最简分数
    PATBasic1062.最简分数1.题目描述:一个分数一般写成两个整数相除的形式:\(N/M\),其中\(M\)不为0。最简分数是指分子和分母没有公约数的分数表示形式。现给定两个不相等的正分数\(N_1/M_1\)和\(N_2/M_2\),要求你按从小到大的顺序列出它们之间分母为\(K\)的最简分数。2.......