洛谷 P2895 [USACO08FEB]Meteor Shower S(bfs

洛谷 P2895 [USACO08FEB]Meteor Shower S(bfs

洛谷 P2895

介绍坑点：

1.坐标不能低于0，但可以超300！

2.流星定时砸下；

3.流星砸下时间已最早的那个为准！

4.如果出不去还要输出-1！

首先，是一道明显的bfs题，要求最短时间，所以用队列记录；

用结构体记录：

1. 坐标x,y
2. 砸下的最早时间
3. 搜索时经过该点的时间
4. flag记录是否搜过

终止条件：如果搜到一个点永远不会被陨石砸到，输出该点时间，或者直到搜索结束也没有出去，输出-1

typedef struct{
    int x,y,step,time,flag=0;//step为砸下时间，time为目前时间,flag记录是否走过
}node;

注意：流星砸下时间以最早的为准！
ps： 简单的广搜题但是这个坑点卡了好久。。。

完整代码：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <math.h>
#include <string>
#include <vector>
#include <map>
#include <stack>
#include <cstdio>
#include <list>
#include <queue>
#include <set>
#include <unordered_map>
#define ll long long
using namespace std;

typedef struct{
    int x,y,step,time,flag=0;
}node;

node k[305][305],temp;
queue<node> q;

int f1[4]={1,0,0,-1},f2[4]={0,1,-1,0};
int main(){
    int m,i,a,x,y,t,xx,yy,ans=0;
    cin>>m;
    for(i=0;i<305;i++){
        for(a=0;a<305;a++) k[i][a].x=i,k[i][a].y=a,k[i][a].step=-1;
    }
    for(i=0;i<m;i++){
        cin>>x>>y>>t;
        if(k[x][y].step==-1)
        k[x][y].step=t;
        else k[x][y].step=min(k[x][y].step,t);
        for(a=0;a<4;a++) {
            xx=x+f1[a],yy=y+f2[a];
            if(xx<0||yy<0||xx>=305||yy>=305) continue;
            if(k[xx][yy].step==-1) k[xx][yy].step=t;
            else k[xx][yy].step=min(k[xx][yy].step,t);
        }
    }
    k[0][0].time=ans;
    k[0][0].flag=1;
    q.push(k[0][0]);
    while(q.empty()==0){
        temp=q.front();
        q.pop();
        ans=temp.time+1;
        for(a=0;a<4;a++){
            xx=temp.x,yy=temp.y;
            xx+=f1[a],yy+=f2[a];
            if(xx<0||yy<0||xx>=305||yy>=305) continue;
            if(k[xx][yy].flag==1) continue;//走过了
            if(k[xx][yy].step==-1) {//找到了
                cout<<ans;
                return 0;
            }
            else if(k[xx][yy].step<=ans) continue;//走不通
            k[xx][yy].flag=1;
            k[xx][yy].time=ans;
            q.push(k[xx][yy]);
        }
    }
    cout<<-1;
}