bfs

BFS就是廣度或者說是寬度優先搜索，用於圖的搜索，每次都是從一個節點開始，向四周都搜索一邊，放進隊列裡面，然後每次從隊列頭開始拿，再重複這個搜索的過程；

因為這樣，他的特別之處在於　“广搜的特性，返回的第一个一定是最短的路径”　！！！

不同於深搜dfs，which is每次都是一個方向一路搜到底，而不是每次向四周都搜索一邊...

來一題：

poj.3278 Catch That Cow

這題找一種需要步數最少的方法，從起始位置a走到目標位置b，走的方式有三種：-1,+1,*2；So，找最短路，用bfs；三種方式，就是每次走三個方向了；

但是有可能會耗時很多導致TLE，所以要加個vis數組剪枝，把訪問過的標誌一下，防止走重複了...

那麼很自然地要注意，-1的情況不能導致vis數組下標為負，並且*2的時候防止數組越界，這兩個問題可以把你RE死...

 1 // poj.3278 Catch That Cow
 2 // bfs
 3 // references:
 4 // http://blog.csdn.net/lyy289065406/article/details/6647886
 5 // http://blog.csdn.net/zhengnanlee/article/details/12952097
 6 #include <iostream>
 7 #include <cstdio>
 8 #include <cstring>
 9 #include <algorithm>
10 #include <queue>
11 
12 using namespace std;
13 
14 const int N = 400015;    //注意因为要乘以2，所以弄大点 
15 
16 struct node {
17     int pos;
18     int count;
19     node():pos(-1), count(0){}
20     node(int a, int b):pos(a), count(b){}
21 };
22 
23 bool vis[N];
24 
25 int main()
26 {
27     int a, b;
28     while(scanf("%d%d", &a, &b) != EOF)    //广搜的特性，返回的第一个一定是最短的路径
29     {
30         memset(vis, 0, sizeof(vis));
31         int ans = 0x3f3f3f3f;
32         queue <node> q;
33         node s(a, 0);
34         vis[a] = 1;
35         q.push(s);
36         while(!q.empty())
37         {
38             node temp = q.front();
39             q.pop();
40             if(temp.pos == b)
41             {
42                 printf("%d
", temp.count);
43                 break;
44             }
45             if(!vis[temp.pos + 1] && temp.pos <= b)    //不剪枝的同学试试输入n=0  k=100000。。。。。。铁定RE
46             {
47                 vis[temp.pos + 1] = 1;
48                 node next1(temp.pos + 1, temp.count + 1);
49                 q.push(next1);
50             }
51             if(!vis[temp.pos - 1] && temp.pos > 0)
52             {
53                 vis[temp.pos - 1] = 1;
54                 node next2(temp.pos - 1, temp.count + 1);
55                 q.push(next2);
56             }
57             if(!vis[temp.pos * 2] && temp.pos <= b)
58             {
59                 vis[temp.pos * 2] = 1;
60                 node next3(temp.pos * 2, temp.count + 1);
61                 q.push(next3);
62             }    
63         }
64     }
65     return 0;
66 }