首页 > 其他分享 >洛谷题单指南-搜索-P2895 [USACO08FEB] Meteor Shower S

洛谷题单指南-搜索-P2895 [USACO08FEB] Meteor Shower S

时间:2024-03-05 16:36:47浏览次数:32  
标签:nx && 格子 int 洛谷题 unsafe Shower 烧焦 Meteor

原题链接:https://www.luogu.com.cn/problem/P2895

题意解读:所谓安全格子,就是在所有流星坠落之后,没有被烧焦的格子,要计算从起点到这些格子任一一个的最短路径,BFS可以解决。

解题思路:

1、读取数据,先把所有流星坠落点以及周围被烧焦的格子进行标记,得到安全格子

2、从起点开始BFS,每走一步之前,要把该时刻被烧焦的格子进行标记,只能向上、下、左、右移动到没有被烧焦的格子中,且不能越界

3、遍历到任一安全格子,输出步数

注意:

测试点14有一个坑,就是人是可以走到坐标>300的格子的,流星能烧焦的格子坐标最多到301,所以如果人走到坐标302的格子,就能到安全格子。

100分代码:

#include <bits/stdc++.h>
using namespace std;

const int M = 50005, N = 305;

struct pos
{
    int x, y;
};

bool unsafe[N][N]; //unsafe[i][j]==true表示被烧焦的格子,unsafe[i][j]==false表示安全格子
map<int, vector<pos>> stars; //保存所有时刻出现的流星
bool flag[N][N]; //标记是否烧焦、以及是否走过
int depth[N][N]; //depth[i][j]表示从起点到(i,j)的步数
queue<pos> q;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

int m, x, y, t;

void bfs()
{
    q.push({0, 0});
    flag[0][0] = true;
    while(q.size())
    {
        pos p = q.front(); q.pop();

        //如果是安全格子,输出结果
        if(!unsafe[p.x][p.y])
        {
            cout << depth[p.x][p.y];
            return;
        }

        //下一个时刻哪些流星会落地,标记烧焦的格子
        vector<pos> s = stars[depth[p.x][p.y] + 1];
        for(auto a : s)
        {
            flag[a.x][a.y] = true;
            for(int i = 0; i < 4; i++)
            {
                int nx = a.x + dx[i], ny = a.y + dy[i];
                if(nx >= 0 && nx <= 300 && ny >= 0 && ny <= 300) flag[nx][ny] = true;
            }
        }
        //遍历四个方向
        for(int i = 0; i < 4; i++)
        {
            int nx = p.x + dx[i], ny = p.y + dy[i];            
            if(!flag[nx][ny] && nx >= 0 && nx <= 302 && ny >= 0 && ny <= 302) //注意人是可以走到300以外的格子的,流星能烧焦的格子最多是301
            {
                depth[nx][ny] = depth[p.x][p.y] + 1;
                flag[nx][ny] = true;
                q.push({nx, ny});
            }
        }
    }

    cout << -1;
}

int main()
{
    cin >> m;
    while(m--)
    {
        cin >> x >> y >> t;
        //标记被烧焦格子
        unsafe[x][y] = true;
        for(int i = 0; i < 4; i++)
        {
            int nx = x + dx[i], ny = y + dy[i];
            if(nx >= 0 && nx <= 300 && ny >= 0 && ny <= 300) unsafe[nx][ny] = true;
        }

        //保存流星
        stars[t].push_back({x, y});
    }

    bfs();

    return 0;
}

 

标签:nx,&&,格子,int,洛谷题,unsafe,Shower,烧焦,Meteor
From: https://www.cnblogs.com/jcwy/p/18054319

相关文章

  • 洛谷题单指南-搜索-P1135 奇怪的电梯
    原题链接:https://www.luogu.com.cn/problem/P1135题意解读:计算A到B至少要按几次电梯,本质上就是求A到B的最短路径,可以通过BFS解决。解题思路:位于每一层,有两种选择:向上、向下BFS搜索直接从A找到B,每扩展一层,层数+1,层数即按电梯次数100分代码:#include<bits/stdc++.h>usingnam......
  • 洛谷题单指南-搜索-P1443 马的遍历
    原题链接:https://www.luogu.com.cn/problem/P1443题意解读:无论是国际象棋还是中国象棋,马的活动范围都是一样的:只不过国际象棋棋子是在格子中,中国象棋棋子是在交点,坐标的变化方式是一样的,根据此活动范围,计算马到达每一个点的最短路径。解题思路:根据马的活动范围,在棋盘内进行B......
  • 洛谷题单指南-搜索-P2392 kkksc03考前临时抱佛脚
    原题链接:https://www.luogu.com.cn/problem/P2392解题思路:参考https://www.cnblogs.com/jcwy/p/18003097前面已经给出了二进制法的代码,这里给出DFS的代码100分代码:#include<bits/stdc++.h>usingnamespacestd;constintN=25;ints1,s2,s3,s4;inta[N],b[N],c[......
  • 洛谷题单指南-搜索-P1219 [USACO1.5] 八皇后 Checker Challenge
    原题链接:https://www.luogu.com.cn/problem/P1219题意解读:八皇后,经典回溯问题。解题思路:逐行摆放棋子,关键在于如何快速判断行、列、正斜(左上到右下)、反斜(右上到左下)方向没有已放其他棋子1、由于逐行摆放,因此行不需要判断通过一个boolcol[N]数组即可判断列上是否已摆放其他棋......
  • 洛谷题单指南-二分查找与二分答案-P3743 kotori的设备
    原题链接:https://www.luogu.com.cn/problem/P3743题意解读:设备使用的时间越久,需要充电的总时间也越多,具备单调性,根据使用的时间,计算需要充电的时间,如果充电总时间<=使用的时间,说明有电量还能富余,使用时间还可以更多,因此只需对使用时间进行二分即可。解题思路:给定设备使用的时间......
  • 洛谷题单指南-二分查找与二分答案-P1163 银行贷款
    原题链接:https://www.luogu.com.cn/problem/P1163题意解读:利率越小,贷款期限和每个月还的钱固定的情况下,越有可能能够还完全部的贷款,具备单调性,因此给定贷款利率、贷款月数、每月还款钱数,可以计算最终贷款还剩下多少,有两种情况:>=0,说明利率可能大了,要试探更小利率;<0,说明利率小了,要......
  • 洛谷题单指南-二分查找与二分答案-P1182 数列分段 Section II
    原题链接:https://www.luogu.com.cn/problem/P1182题意解读:每段和的最大值越小,则分段数就越多,因此可以通过给定每段和的最大值,将分段数划分为两类:<=M,>M,对每段和的最大值进行二分即可。解题思路:二分的判定条件为,给定每段和的最大值,计算分段数,计算逻辑如下:依次遍历每一个数,求当前......
  • 洛谷题单指南-二分查找与二分答案-P3853 [TJOI2007] 路标设置
    原题链接:https://www.luogu.com.cn/problem/P3853题意解读:相邻路标的最大距离即空旷指数,空旷指数越小,用的路标越多,因此可以根据空旷指数将使用路标情况分成两类:路标数<=K,路标数>K,对空旷指数进行二分即可。解题思路:二分的判定条件为,给定空旷指数,计算需要的路标数只需遍历每两......
  • 洛谷题单指南-二分查找与二分答案-P2678 [NOIP2015 提高组] 跳石头
    原题链接:https://www.luogu.com.cn/problem/P2678题意解读:最短跳跃距离越大,要移走的石头就越多,因此可以根据最短跳跃距离的不同把情况分为两类:移走的石头数<=M、移走的石头数>M,对最短跳跃距离二分即可。解题思路:二分的判定条件如下:对于给定最短跳跃距离,需要计算移走的石头数,......
  • 洛谷题单指南-二分查找与二分答案-P2440 木材加工
    原题链接:https://www.luogu.com.cn/problem/P2440题意解读:切出来的长度越短,则段数越多,可以通过二分长度来解决。解题思路:二分的关键在于判定条件,此题就是对二分到的长度计算可以切割的段数,如果段数大于等于k,则满足要求,可以继续加大长度。注意点:1、计算切割出来的段数是累加:每......