P2895 [USACO08FEB]Meteor Shower S

P2895 [USACO08FEB]Meteor Shower S

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N = 310;

int x, y, t;
int g[N][N];
bool st[N][N];
int dx[5] = {0, -1, 0, 1, 0}, dy[5] = {0, 0, 1, 0, -1};

struct node
{
    int x0, y0, t0;
};

void bfs(int x, int y, int t)
{
    queue<node> q;
    q.push({x, y, t});
    st[x][y] = true;
    
    while(q.size())
    {
        node t = q.front();
        q.pop();
        
        if(g[t.x0][t.y0] == -1)
        {
            cout << t.t0 << endl;
            return ;
        }
        
        for(int i = 1; i <= 4; i ++)
        {
            int a = t.x0 + dx[i], b = t.y0 + dy[i];
            if(a < 0 || b < 0 || st[a][b]) continue;
            if(t.t0 + 1 >= g[a][b] && g[a][b] != -1) continue;
            
            st[a][b] = true;
            q.push({a, b, t.t0 + 1});
        }
    }
    cout << -1;     //注意如果走不到安全点的话输出-1
}

int main ()
{
    int n;
    cin >> n;
    memset(g, -1, sizeof g);        //因为有流星是在0时落下，所以不能用0来判断是否有流星落下
    for(int i = 0; i < n; i ++)
    {
        cin >> x >> y >> t;
        for(int i = 0; i < 5; i ++)
        {
            int a = x + dx[i], b = y + dy[i];
            if(a < 0 || b < 0 || (g[a][b] != -1 && g[a][b] <= t)) continue;     //只有流星落下的时间比之前已经落下的更早才会被替换
            g[a][b] = t;
        }
    }
    
    bfs(0, 0, 0);
    
    return 0;
}

心得体会：

1. 将坐标和当前时间打包成结构体一起入队出队
2. 养成memset -1 的习惯，用 -1 表示初始状态，而不偷懒用 0 表示初始状态
3. 注意坑点：流星从0落下； 流星落下时间会被更早的替换，而不能无脑替换
4. 与P3395 路障类似