Meteor Shower S(bfs)

Meteor Shower S(bfs)

题目:

见

思路:

搬自洛谷题解:
介绍坑点：
1.坐标不能低于0，但可以超300！
2.流星定时砸下；
3.流星砸下时间已最早的那个为准！这个尤其重要！！！
4.如果出不去还要输出-1！
5.首先，是一道明显的bfs题，要求最短时间，所以用队列记录

代码:

#include<iostream>
#include<queue>
#include<cstring>
#include<climits>
using namespace std;
const int N=310;
int g[N][N],ans[N][N],visit[N][N];
typedef pair<int,int> PII;
queue<PII> q;
int m;
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
int main()
{cin>>m;for(int i=0;i<N;i++)for(int j=0;j<N;j++)g[i][j]=INT_MAX;for(int i=1;i<=m;i++){int x,y,s;cin>>x>>y>>s;if(s<g[x][y])//之前这里没注意WA四个点g[x][y]=s;for(int i=0;i<4;i++){int nx=x+dx[i],ny=y+dy[i];if(nx>=0&&ny>=0&&s<g[nx][ny])//这里判断条件同上g[nx][ny]=s;}}q.push({0,0});visit[0][0]=1;int flag=0;while(!q.empty()){int x=q.front().first,y=q.front().second;q.pop();if(g[x][y]==INT_MAX){flag=1;cout<<ans[x][y]<<endl;break;}int s=ans[x][y]+1;for(int i=0;i<4;i++){int nx=x+dx[i],ny=y+dy[i];if(nx>=0&&ny>=0&&s<g[nx][ny]&&!visit[nx][ny]){visit[nx][ny]=1;q.push({nx,ny});ans[nx][ny]=s;}}}if(!flag)cout<<-1<<endl;return 0;
}