[搜索]USACO Feb08 Silver 流星雨 meteor 解題報告

題目連結：http://cogs.yeefanblog.tk/t/138

Title: 流星雨

Input: meteor.in

Output: meteor.out

Time Limit: 1000 ms

Memory Limit: 128 MB

Level: ★☆

貝茜聽說了一個駭人聽聞的消息：一場流星雨即將襲擊整個農場，由於流星體積過大它們無法在撞擊到地面前燃燒殆盡，屆時將會對它撞到的一切東西造成毀 滅性的打擊。很自然地，貝茜開始擔心自己的安全問題。以FJ牧場中最聰明的奶牛的名譽起誓，她一定要在被流星砸到前，到達一個安全的地方（也就是說，一塊 不會被任何流星砸到的土地）。如果將牧場放入一個直角座標系中，貝茜現在的位置是原點，並且，貝茜不能踏上一塊被流星砸過的土地。

根據預報，一共有M顆流星(1 <= M <= 50,000)會墜落在農場上，其中第i顆流星會在時刻T_i (0 <= T_i <= 1,000)砸在座標為(X_i, Y_i) (0 <= X_i <= 300；0 <= Y_i <= 300)的格子裡。流星的力量會將它所在的格子，以及周圍4個相鄰的格子都化為焦土，當然貝茜也無法再在這些格子上行走。

貝茜在時刻0開始行動，它只能在第一象限中，平行於座標軸行動，每1個時刻中，她能移動到相鄰的（一般是4個）格子中的任意一個，當然目標格子要沒有被燒焦才行。如果一個格子在時刻t被流星撞擊或燒焦，那麼貝茜只能在t之前的時刻在這個格子裡出現。

請你計算一下，貝茜最少需要多少時間才能到達一個安全的格子。

程序名: meteor

 

輸入格式:

• 第1行: 1個正整數：M

• 第2..M+1行: 第i+1行為3個用空格隔開的整數：X_i，Y_i，以及T_i

輸入樣例 (meteor.in):

4

0 0 2

2 1 2

1 1 2

0 3 5

輸入說明:

一共有4顆流星將墜落在農場，它們落地點的座標分別是(0, 0)，(2, 1)，(1, 1)以及(0, 3)，時刻分別為2，2，2，5。

    t = 0                t = 2              t = 5
5|. . . . . . .     5|. . . . . . .     5|. . . . . . .    
4|. . . . . . .     4|. . . . . . .     4|# . . . . . .   * = 流星落點
3|. . . . . . .     3|. . . . . . .     3|* # . . . . .  
2|. . . . . . .     2|. # # . . . .     2|# # # . . . .   # = 行走禁區
1|. . . . . . .     1|# * * # . . .     1|# # # # . . .   
0|B . . . . . .     0|* # # . . . .     0|# # # . . . .   
  --------------      --------------      -------------- 
  0 1 2 3 4 5 6       0 1 2 3 4 5 6       0 1 2 3 4 5 6 

輸出格式:

• 第1行: 輸出1個整數，即貝茜逃生所花的最少時間。如果貝茜無論如何都無法在流星雨中存活下來，輸出-1

輸出樣例 (meteor.out):

5

輸出說明:

如果我們觀察在t=5時的牧場，可以發現離貝茜最近的安全的格子是(3,0)——不過由於早第二顆流星落地時，貝茜直接跑去(3,0)的路 線就被封死了。離貝茜第二近的安全格子為(4,0)，但它的情況也跟(3,0)一樣。再接下來的格子就是在(0,5)-(5,0)這條直線上。在這些格子 中，(0,5)，(1,4)以及(2,3)都能在5個單位時間內到達。

5|. . . . . . .   
4|. . . . . . .   
3|3 4 5 . . . .    某個合法的逃生方案中
2|2 . . . . . .    貝茜每個時刻所在地點
1|1 . . . . . .   
0|0 . . . . . .   
  -------------- 
  0 1 2 3 4 5 6

【分析】

為什麼這題這麼殘忍，竟要燒死我們可愛的Bessie！！ 我很不情願輸出-1啊！！

這題，嗯，先初始化到每個地方的時間為最大值，然後是預處理，我們需要得到每個地方被

流星摧毀的最早時間，如果不會被流星摧毀，就是最大值。 依次讀取流星墜落的地點，

把那個點和四周的4個點更新一下被摧毀的時間，就這樣完成預處理。

然後就是搜索了，跟普通的FloodFill差不多～廣度優先搜索即可。BYVoid大牛說深搜需要

優化才能過。我寫的STL queue，挺快的。 為了防止一個點多次入隊並形成迴路，需要開一

個二維數組，記錄Bessie到每個點的最短時間，防止重複入隊。

【我的代碼】

裸代碼RawCode 

C++语言: Codee#25367

001 /*
002 *Problem: USACO meteor
003 *Author: Yee-fan Zhu
004 *Website:http://blog.yeefanblog.tk/
005 *Email:zyfworks@gmail.com
006 *School:Henan Experimental High School
007 *Method: Search FloodFill BFS C++_STL_queue
008 *Data: Jan 23,2012
009 */
010 #include <iostream>
011 #include <cstdio>
012 #include <queue>
013 #include <cstdlib>
014 using namespace std;
015
016 const int MAXN=302;
017 const int Step[5][2]={{0,0},{1,0},{-1,0},{0,1},{0,-1}};
018 const int INF=0x7fffffff;
019 int M;
020 int Map[MAXN][MAXN];
021 int MinTime[MAXN][MAXN];
022
023 int Ans=-1;
024 int Min(int a,int b)
025 {
026     return (a>b?b:a);
027 }
028
029 void init()
030 {
031    
032     for (int i=0;i<=301;i++)
033         for (int j=0;j<=301;j++)
034             Map[i][j]=INF,MinTime[i][j]=INF;
035    
036     scanf("%d\n",&M);
037     int x,y,t;
038     int tx,ty;
039     for (int i=1;i<=M;i++)
040     {
041         scanf("%d %d %d\n",&x,&y,&t);
042        
043         for(int j=0;j<=4;j++)
044         {
045             tx=x+Step[j][0];
046             ty=y+Step[j][1];
047             if(tx>=0 && ty>=0)
048                 Map[tx][ty]=Min(t,Map[tx][ty]);
049         }
050     }
051 }
052
053 class QUEUE
054 {
055 public:
056     int x,y,t;
057 };
058
059 queue<QUEUE>Q;
060 void bfs()
061 {
062     QUEUE now,next;
063     now.x=0,now.y=0,now.t=0;
064     int tx,ty,tt;
065     int nx,ny,nt;
066    
067     Q.push(now);
068     while(!Q.empty())
069     {
070         now=Q.front();
071         Q.pop();
072         tx=now.x,ty=now.y,tt=now.t;
073         if(Map[tx][ty]<=tt)
074             continue;
075         if(Map[tx][ty]==INF)
076         {
077             Ans=tt;
078             break;
079         }
080         nt=tt+1;
081         for (int i=1;i<=4;i++)
082         {
083             nx=tx+Step[i][0];
084             ny=ty+Step[i][1];
085             if(nx<0 || ny<0)
086                 continue;
087             if(Map[nx][ny]<=nt)
088                 continue;
089             if(MinTime[nx][ny]<=nt)
090                 continue;
091             next.x=nx,next.y=ny,next.t=nt;
092             MinTime[nx][ny]=nt;
093             Q.push(next);
094         }
095     }
096     printf("%d\n",Ans);
097 }
098
099 int main()
100 {
101     freopen("meteor.in","r",stdin);
102     freopen("meteor.out","w",stdout);
103     init();
104     bfs();
105     return 0;
106 }