题意： 有个**要看流星雨，可是流星雨会砸死他的。。。 给出n个流星雨下落的坐标，时间，如果那个**在下落坐标或是上下左右就会gg，问你他最短跑到流星雨打不到的地方的时间。 思路： ①：预处理出一个矩阵，每个坐标代表最早下落时间； ②：直接bfs…中间要标记掉走到的坐标，不能往回走，还是满基础的。
贴一发挫code………….
#include<cstdio> #include<map> #include<queue> #include<math.h> #include<string.h> #include<algorithm> using namespace std; #define eps 1e-8 typedef __int64 LL; const int INF=-1; const int N=304; int dx[4]={0,0,-1,1}; int dy[4]={1,-1,0,0}; bool vis[N][N]; int ma[N][N]; int n; bool Judge(int x,int y) { if(x<0||y<0||x>=302||y>=302) return 0; return 1; } void Init() { int x,y,t; memset(ma,-1,sizeof(ma)); for(int i=0;i<n;i++) { scanf("%d%d%d",&x,&y,&t); if(ma[x][y]==-1) ma[x][y]=t; else ma[x][y]=min(t,ma[x][y]); for(int k=0;k<4;k++) { int xx=x+dx[k]; int yy=y+dy[k]; if(Judge(xx,yy)) { if(ma[xx][yy]==-1) ma[xx][yy]=t; else ma[xx][yy]=min(t,ma[xx][yy]); } } } } struct asd{ int x,y; int step; }; asd now,next; queue<asd>q; int bfs() { int x,y,tp; while(!q.empty()) q.pop(); memset(vis,0,sizeof(vis)); now.x=0; now.y=0; now.step=0; vis[0][0]=1; q.push(now); while(!q.empty()) { now=q.front();q.pop(); x=now.x; y=now.y; tp=now.step; if(ma[x][y]==-1) return tp; for(int i=0;i<4;i++) { int xx=x+dx[i]; int yy=y+dy[i]; next.x=xx; next.y=yy; next.step=tp+1; if(!Judge(xx,yy)||vis[xx][yy]) continue; if(ma[xx][yy]==-1) return next.step; if(next.step>=ma[xx][yy]) continue; vis[xx][yy]=1; q.push(next); } } return -1; } int main() { scanf("%d",&n); Init(); int ans; ans=bfs(); printf("%d\n",ans); return 0; }