【POJ 3669 Meteor Shower】简单BFS

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <queue>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 const int INF=10000;
 8 const int MAX_N=302;//流星雨落在（300，300）以内，所以最近的安全点一定在（302,302）以内
 9 int m;
10 int G[MAX_N+1][MAX_N+1];
11 int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
12 int vis[MAX_N+1][MAX_N+1];
13 
14 struct Node
15 {
16     int x,y,time;
17     Node(){}
18     Node(int xx,int yy,int t):x(xx),y(yy),time(t){}
19 };
20 
21 int inside(int x,int y)
22 {
23     if(x<0||y<0||MAX_N<x||MAX_N<y) return 0;
24     else return 1;
25 }
26 
27 int bfs()
28 {
29     memset(vis,0,sizeof(vis));
30     if(G[0][0]==INF) return 0;
31     if(G[0][0]==0) return -1;//当G[0][0]==1时，不代表没希望逃走。。。
32     //因为G数组经过预处理了，把每颗流星雨的影响都表达为每个点的*时间
33     queue<Node> que;
34     que.push(Node(0,0,0));
35     vis[0][0]=1;
36     while(!que.empty())
37     {
38         Node cur=que.front();
39         que.pop();
40         if(G[cur.x][cur.y]==INF) return cur.time;
41         for(int i=0;i<4;i++)
42         {
43             int nx=cur.x+dx[i];
44             int ny=cur.y+dy[i];
45             if(!inside(nx,ny)) continue;
46             if(vis[nx][ny]) continue;
47             if(G[nx][ny]<=cur.time+1) continue;
48             que.push(Node(nx,ny,cur.time+1));
49             vis[nx][ny]=1;
50         }
51     }
52     return -1;
53 }
54 
55 int main()
56 {
57     freopen("3669.txt","r",stdin);
58     scanf("%d",&m);
59     for(int i=0;i<=MAX_N;i++)
60         for(int j=0;j<=MAX_N;j++)
61             G[i][j]=INF;
62     for(int i=0;i<m;i++)
63     {
64         int x,y,t;
65         scanf("%d%d%d",&x,&y,&t);
66         G[x][y]=min(t,G[x][y]);
67         for(int i=0;i<4;i++)
68         {//把G数组预处理为每个点的最早*时间
69             int nx=x+dx[i];
70             int ny=y+dy[i];
71             if(!inside(nx,ny)) continue;
72             G[nx][ny]=min(t,G[nx][ny]);
73         }
74     }
75     printf("%d
",bfs());
76     return 0;
77 }