USACO Dec07 泥潭 mud 解題報告

Title: 泥潭

Input: mud.in

Output: mud.out

Time Limit: 1000 ms

Memory Limit: 128 MB

Level: ★☆

譯 by CmYkRgB123

描述

Farmer John在早晨6點準時去給貝茜擠奶，然而昨天晚上下了大雨，他的牧場變得泥濘不堪了。Farmer John的家在座標平面的 (0,0) 處，貝茜在 (X, Y) (-500 ≤ X ≤ 500; -500 ≤ Y ≤ 500)。他看見了所有的 N (1 ≤ N ≤ 10,000) 個泥潭，分別在 (Ai, Bi) (-500 ≤ Ai ≤ 500; -500 ≤ Bi ≤ 500) 。每個泥潭只佔一個點的位置。

Farmer John 剛剛買了新的靴子，他絕對不想把靴子踩進泥潭弄髒，而他又想儘快的找到貝茜。他已經快晚了，因爲他花了大量的時間來找到所有的泥潭的位置。 Farmer John 只能平行於座標軸移動，每次移動一個單位。請你幫助 Farmer John 找到一條路，使得 Farmer John 能夠最快的找到貝茜，而且不會弄髒靴子。我們約定一定存在一條路使 Farmer John 找到貝茜。

輸入

* 第 1 行: 三個整數 X, Y, N

* 第 2..N+1 行: 第 i+1 行 包含兩個整數 Ai , Bi

輸出

* 第 1 行: Farmer John 能夠最快的找到貝茜，而且不會弄髒靴子，要走的最小的距離。

樣例輸入

1 2 7

0 2

-1 3

3 1

1 1

4 2

-1 1

2 2

樣例輸出

11

【分析】

廣搜？記憶化搜索？ 嗯，就是這一類的題，在搜索中做決策的記憶化搜素。

開兩個數組，F[i][j]記錄走到(i,j)最小步數，Map[i][j]記錄(i,j)是否可走。

然後就像障礙訓練場那樣，是一個BFS過程，先把Beesie的位置入隊，然後依次出隊向四周擴展，如果能使四周的一個點取得更少的到達步數，那麼就更新並且入隊。最後只要輸出到達終點的F值即可。

需要注意的是，由於存在負數，所以要整體平移501個單位以化負為正。

我這題一共Submit了1次，直接AC。但是調試過程中，G++一直報越界，越界的位置在Q.front()的地方，這front()函數既沒有銷毀內存也沒有申請內存，卻偏偏在這裡越界，我還以為出鬼了呢。  其實是我初始化的時候越界了（我都幾個有月沒越過界了～），還是Zeray童鞋幫忙找出來的錯誤～因為編譯器報queue越界，所以我一直盯著queue看～我承認我SB了～

算了，不扯了，Code Time。

【我的代碼】

裸代碼RawCode

C++语言: Codee#25445

01 /*
02 *Problem: USACO Dec07 mud
03 *Author: Yee-fan Zhu
04 *Website: http://zhuyf.tk/
05 *Method: BFS  Memorize-Search
06 */
07 #include <cstdio>
08 #include <cstdlib>
09 #include <queue>
10 using namespace std;
11 const int MAX=10000000;
12 const int MAXN=1010;
13 const int SHIFT=501; 
14 int X,Y,N;
15 int F[MAXN][MAXN];
16 int Map[MAXN][MAXN];
17
18 void init()
19 {
20    
21     for(int i=1;i<MAXN;i++)
22         for(int j=1;j<MAXN;j++)
23             Map[i][j]=0,F[i][j]=MAX;
24    
25     scanf("%d %d %d\n",&X,&Y,&N);
26     X+=SHIFT,Y+=SHIFT;
27     F[X][Y]=0;
28     int a,b;
29     for(int i=1;i<=N;i++)
30     {
31         scanf("%d %d\n",&a,&b);
32         a+=SHIFT,b+=SHIFT;
33         Map[a][b]=1;
34     }
35 }
36
37 class QUEUE
38 {
39 public:
40     int x,y;
41 };
42 const int step[5][2]={{0,0},{1,0},{-1,0},{0,1},{0,-1}};
43 queue<QUEUE>Q;
44
45 void bfs()
46 {
47     QUEUE tmp,nxt;
48     int nx,ny,nf;
49     int tx,ty,tf;
50     tmp.x=X,tmp.y=Y;
51     Q.push(tmp);
52    
53     while(!Q.empty())
54     {
55         tmp=Q.front();
56         Q.pop();
57         tx=tmp.x,ty=tmp.y;
58         tf=F[tx][ty];
59         for(int i=1;i<=4;i++)
60         {
61             nx=tx+step[i][0];
62             ny=ty+step[i][1];
63             if(nx<1 || nx>MAXN || ny<1 || ny>MAXN)
64                 continue;
65             if(Map[nx][ny]==1)
66                 continue;
67             nf=tf+1;
68             if(F[nx][ny]<=nf) 
69                 continue;
70             F[nx][ny]=nf;
71             nxt.x=nx,nxt.y=ny;
72             Q.push(nxt);
73         }
74     }
75     printf("%d\n",F[SHIFT][SHIFT]);
76 }
77
78 int main()
79 {
80     freopen("mud.in","r",stdin);
81     freopen("mud.out","w",stdout);
82     init();
83     bfs();
84     return 0;
85 }