[刷题笔记] Luogu P2895 Meteor Shower S

Problem

Solution

显然bfs，只不过有了限定条件，有实时的流星雨

这里提供两种做法：

Solution 1

这也是我一开始的做法

模拟实时流星，由于bfs是按层搜的，是严格按照时间递增搜的，故可以模拟实时放流星。
需要注意放流星的时间，如果第\(t\)秒有流星，则该秒不可以走，需要在每一秒前放流星。

那么如何判定该点安全呢？
可以开两个数组，一个存实时流星，另一个存是否有流星，具体见代码

实现的时候还需要注意Bessie可以走出300，300只是流星的界限。

Code 1:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#define INF 0x3f3f3f3f
#define N 1010
#define M 500010
using namespace std;
int m;
int mapp_boom[N][N];
int mapp[N][N];
int vis[N][N];
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
struct Node
{
    int x,y,t;
}rock[M];
bool get_ans = false;
bool check_add(int x,int y) 
{
    return x >= 0 && x <= 390 && y >= 0 && y <= 390; //开大界限
}
void boom(int t)
{
    for(int i=1;i<=m;i++) 
    {
        if(t == rock[i].t) 
        {
            mapp[rock[i].x][rock[i].y] = 1;
            for(int j=0;j<4;j++)
            {
                int ax = rock[i].x + dx[j];
                int ay = rock[i].y + dy[j];
                if(check_add(ax,ay)) mapp[ax][ay] = 1; //实时放流星
            }
        }
    }
}
void bfs()
{
    queue <Node> q;
    q.push(Node{0,0,0});
    vis[0][0] = 0;
    while(!q.empty())
    {
        Node p = q.front();
        q.pop();
        boom(vis[p.x][p.y]+1);
        if(!mapp_boom[p.x][p.y]) //如果该点安全
        {
            cout<<vis[p.x][p.y]<<endl;
            get_ans = true;
            return;
        }
        for(int i=0;i<4;i++)
        {
            int ax = p.x + dx[i];
            int ay = p.y + dy[i];
            if(check_add(ax,ay) && !mapp[ax][ay] && vis[ax][ay] == INF) 
            {
                vis[ax][ay] = vis[p.x][p.y] + 1;
                q.push(Node{ax,ay,0});
             //   boom(vis[ax][ay]);
            }
        }
    }
}
int main()
{
    scanf("%d",&m);
    memset(vis,INF,sizeof(vis));
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&rock[i].x,&rock[i].y,&rock[i].t);
        mapp_boom[rock[i].x][rock[i].y] = 1;
        for(int j=0;j<4;j++) 
        {
            int ax = rock[i].x + dx[j];
            int ay = rock[i].y + dy[j];
            if(check_add(ax,ay)) mapp_boom[ax][ay] = 1; //标记该点危险
        }
    }
    boom(0); //需要注意放流行要在该秒前放
    bfs();
    if(!get_ans) printf("-1\n");
    return 0;
}

Solution 2

教练提供的思路，相较于Sol 1更加干净利落一点

我们可以开一个数组记录该点被炸的时间（预处理），然后普通bfs即可

预处理的时候如果该流星炸这个点的时间比原来流星炸这个点的时间早就可以覆盖。

需要注意第0秒可能有流星，所以没有流星不能用0表示。被卡了ww

相较于Sol 1，只需要一个数组就可以完成流星时间以及是否有流星两个操作，非常简洁。

Code 2:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#define N 1010
#define INF 0x3f3f3f3f
using namespace std;
bool get_ans = false;
typedef pair<int,int> PAIR;
int m;
int boom[N][N];
int vis[N][N];
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
struct Node
{
    int x,y,t;
}b[500000];
bool cmp(Node a,Node b)
{
    return a.t < b.t;
}
void bfs()
{
    queue <PAIR> q;
    q.push(PAIR(0,0));
    vis[0][0] = 0;
    while(!q.empty())
    {
        PAIR p = q.front();
        q.pop();
        if(boom[p.first][p.second] == -1) 
        {
            cout<<vis[p.first][p.second]<<endl;
            get_ans = true;
            return;
        }
        for(int i=0;i<4;i++)
        {
            int ax = p.first + dx[i];
            int ay = p.second + dy[i];
            if(ax>=0&&ax<=400&&ay>=0&&ay<=400&&vis[ax][ay] == INF&&(vis[p.first][p.second]+1 < boom[ax][ay] || boom[ax][ay] == -1))
            {
                vis[ax][ay] = vis[p.first][p.second] + 1;
                q.push(PAIR(ax,ay));
            }
        }
    }
}
int main()
{
    memset(boom,-1,sizeof(boom));//不得使用0
    memset(vis,INF,sizeof(vis));
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&b[i].x,&b[i].y,&b[i].t); 
    }
    for(int i=1;i<=m;i++)
    {
        if(boom[b[i].x][b[i].y] == -1 || b[i].t < boom[b[i].x][b[i].y])
            boom[b[i].x][b[i].y] = b[i].t;
        for(int j=0;j<4;j++) 
        {
            int ax = b[i].x+dx[j];
            int ay = b[i].y+dy[j];
            if(ax>=0&&ax<=400&&ay>=0&&ay<=400&&(boom[ax][ay] == -1 || b[i].t < boom[ax][ay])) boom[ax][ay] = b[i].t;
        }
    }
    bfs();
    if(!get_ans) cout<<"-1"<<endl;
    return 0;
}

Double Exp
和流星几乎一样，也可以使用这两种实现方法，只是路障砸下的时间可以走而已.