深度優先搜索（DFS）和廣度優先搜索（BFS）是基本的暴力技術，常用於解決圖、樹的遍歷問題。 首先考慮演算法思路。以老鼠走迷宮為例： （1）：一隻老鼠走迷宮。它在每個路口都選擇先走右邊，直到碰壁無法繼續前進，然後回退一步，這一次走左邊，接著繼續往下走。用這個辦法能走遍所有的路，而且不會重覆。這個思路就 ...
深度優先搜索（DFS）和廣度優先搜索（BFS）是基本的暴力技術，常用於解決圖、樹的遍歷問題。
首先考慮演算法思路。以老鼠走迷宮為例：
（1）：一隻老鼠走迷宮。它在每個路口都選擇先走右邊，直到碰壁無法繼續前進，然後回退一步，這一次走左邊，接著繼續往下走。用這個辦法能走遍所有的路，而且不會重覆。這個思路就是DFS。
（2）：一群老鼠走迷宮。假設老鼠是無限多的，這群老鼠進去後，在每個路口派出部分老鼠探索沒有走過的路。走某條路的老鼠，如果碰壁無法前進，就停下；如果到達的路口已經有其他的老鼠探索過了，也停下。很顯然，所有的道路都會走到，而且不會重覆。這個思路就是BFS。
There is a rectangular room, covered with square tiles. Each tile is colored either red or black. A man is standing on a black tile. From a tile, he can move to one of four adjacent tiles. But he can't move on red tiles, he can move only on black tiles.
Write a program to count the number of black tiles which he can reach by repeating the moves described above.InputThe input consists of multiple data sets. A data set starts with a line containing two positive integers W and H; W and H are the numbers of tiles in the x- and y- directions, respectively. W and H are not more than 20.
There are H more lines in the data set, each of which includes W characters. Each character represents the color of a tile as follows.
'.' - a black tile
'#' - a red tile
'@' - a man on a black tile(appears exactly once in a data set)
OutputFor each data set, your program should output a line which contains the number of tiles he can reach from the initial tile (including itself).
Sample Input6 9 ....#. .....# ...... ...... ...... ...... ...... #@...# .#..#. 11 9 .#......... .#.#######. .#.#.....#. .#.#.###.#. .#.#..@#.#. .#.#####.#. .#.......#. .#########. ........... 11 6 ..#..#..#.. ..#..#..#.. ..#..#..### ..#..#..#@. ..#..#..#.. ..#..#..#.. 7 7 ..#.#.. ..#.#.. ###.### ...@... ###.### ..#.#.. ..#.#.. 0 0Sample Output
45 59 6 13
題目大意：“#”相當於不能走的陷阱或牆壁，“.”是可以走的路。從@點出發，統計所能到達的地點總數
代碼一：這是初學並查集時硬著頭皮用並查集的演算法解決了BFS的問題
1 #include<iostream> 2 using namespace std; 3 4 const int h = 22; 5 char map[h][h]; 6 int key[h*h]; 7 int rrank[h*h]; 8 int n,m,dx,dy; 9 10 int find(int a){ 11 return a==key[a]? a : key[a]=find(key[a]); 12 } 13 14 void key_union(int a,int c){ 15 int fa = find(a); 16 int fc = find(c); 17 if(rrank[fa]>rrank[fc]) 18 key[fc] = fa; 19 else{ 20 key[fa] = fc; 21 if(rrank[fa]==rrank[fc]) 22 rrank[fc]++; 23 } 24 } 25 26 int num(int a){ 27 int k = find(a); 28 int ans = 0; 29 for(int i=1;i<=m;i++) 30 for(int j=1;j<=n;j++) 31 if(find(i*n+j)==k) 32 ans++; 33 34 return ans; 35 } 36 37 int main() 38 { 39 while(scanf("%d %d",&n,&m)!=EOF){ 40 if(n==0&&m==0) break; 41 for(int i=1;i<=m;i++){ 42 cin.get(); 43 for(int j=1;j<=n;j++){ 44 scanf("%c",&map[i][j]); 45 if(map[i][j]!='#') key[i*n+j] = i*n+j; 46 else key[i*n+j] = 0; 47 if(map[i][j]=='@'){//找到@的坐標 48 dx = i; 49 dy = j; 50 map[i][j] = '.'; 51 } 52 } 53 } 54 55 for(int i=1;i<m;i++){ 56 for(int j=1;j<n;j++){ 57 if(key[i*n+j]){ 58 if(key[i*n+j+1]) 59 key_union(i*n+j,i*n+j+1); 60 if(key[i*n+n+j]) 61 key_union(i*n+n+j,i*n+j); 62 } 63 } 64 if(key[i*n+n]) 65 if(key[i*n+2*n]) 66 key_union(i*n+2*n,i*n+n); 67 } 68 for(int i=1;i<n;i++) 69 if(key[m*n+i]) 70 if(key[m*n+i+1]) 71 key_union(m*n+i,m*n+i+1); 72 73 int ans = num(dx*n+dy); 74 printf("%d\n",ans); 75 } 76 }View Code
代碼二：這是還分不清DFS和BFS時寫的DFS演算法（比後面的BFS要簡潔很多，不知道為什麼作為BFS的例題放在這裡）
1 #include<iostream> 2 using namespace std; 3 4 int mov[4][2] = {-1,0,1,0,0,-1,0,1}; 5 int sum,w,h; 6 char s[21][21]; 7 8 void dfs(int x,int y){ 9 sum++;//計數 10 s[x][y] = '#'; 11 for(int i=0;i<4;++i){//四個方向前進 12 int tx = x+mov[i][0]; 13 int ty = y+mov[i][1]; 14 15 if(s[tx][ty]=='.' && tx>=0 && tx<h && ty>=0 && ty<w) 16 dfs(tx,ty);//判斷該點可行後進入dfs 17 } 18 } 19 20 int main() 21 { 22 int x,y; 23 while(scanf("%d %d",&w,&h)!=EOF){ 24 if(w==0&&h==0) break; 25 for(int i=0;i<h;i++){ 26 cin.get(); 27 for(int j=0;j<w;j++){ 28 scanf("%c",&s[i][j]); 29 if(s[i][j]=='@'){//起點 30 x = i; 31 y = j; 32 } 33 } 34 } 35 sum = 0; 36 dfs(x,y); 37 printf("%d\n",sum); 38 } 39 return 0; 40 }View Code
代碼三：引自《演算法競賽入門到進階》中的解題代碼 BFS演算法
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 char room[23][23]; 5 int dir[4][2] = { //左上角的坐標是(0,0) 6 {-1, 0}, //向左 7 {0, -1}, //向上 8 {1, 0}, //向右 9 {0, -1} //向下 10 }; 11 12 int Wx, Hy, num; 13 #define check(x, y)(x<Wx && x>=0 && y>=0 && y<Hy) //是否在room中 14 struct node{int x, y}; 15 16 void BFS(int dx, int dy){ 17 num = 1; 18 queue<node> q; 19 node start, next; 20 start.x = dx; 21 start.y = dy; 22 q.push(start);//插入隊列 23 24 while(!q.empty()){//直到隊列為空 25 start = q.front();//取隊首元素，即此輪迴圈的出發點 26 q.pop();//刪除隊首元素（以取出） 27 28 for(int i=0; i<4; i++){//往左上右下四個方向逐一搜索 29 next.x = start.x + dir[i][0]; 30 next.y = start.y + dir[i][1]; 31 if(check(next.x, next.y) && room[next.x][next.y]=='.'){ 32 room[next.x][next.y] = '#';//標記已經走過 33 num ++;//計數 34 q.push(next);//判斷此點可行之後，插入隊列，待迴圈判斷 35 } 36 } 37 } 38 } 39 40 int main(){ 41 int x, y, dx, dy; 42 while(~scanf("%d %d",&Wx, &Hy)){ 43 if(Wx==0 && Hy==0) 44 break; 45 for(y=0; y<Hy; y++){ 46 for(x=0; x<Wx; x++){ 47 scanf("%d",&room[x][y]); 48 if(room[x][y] == '@'){//找到起點坐標 49 dx = x; 50 dy = y; 51 } 52 } 53 } 54 num = 0;//初始化 55 BFS(dx, dy); 56 printf("%d\n",num); 57 } 58 return 0; 59 }View Code
這裡暫時整理出了此題的關於DFS和BFS演算法的代碼，DFS相對好理解，遞歸的思想早有接觸，相對易用；BFS還涉及到queue隊列的知識，初學時理解困難，即使此處整理出，也不能保證下次遇到時還能寫的出來。
代碼一用的是並查集的思想，因為第一次做這個題目的時候剛學並查集，新鮮就拿出來用了，確實是磨破了頭皮，尤其當看到DFS的代碼以後，我現在再拿出來都不敢相信這是我當時寫的代碼？並查集的思想需要掌握，但是遇題還是要先判斷清楚類型，選擇相對簡易方便、以及自己掌握熟練的演算法。
代碼二是在模糊地聽完了DFS和BFS以後寫出來的代碼，也是我現在最能接受的簡易代碼，遞歸的運用關鍵在於準確找到前後的聯繫，遞歸的代碼看上去簡單，但是真的遇到新題，可就有的折騰了。這類題型中不管DFS還是BFS都有相似的check部分，即在走出下一步之前，要判斷將要走的點，是否在給定範圍之內（也有可能在自己的數組中越界），並有相關標記，表示此處來過，避免重覆計數，防止遞歸或迴圈沒有盡頭。
代碼三是書上的BFS演算法，應該是標準的“模板了”，現在關於vector、queue、map之類的STL序列容器理解不深，掌握不全，運用不好，就算抄模板，也要多練習相關題目,熟悉此類題型的技巧規則。queue的.front() .pop() .push()時運用BFS解決題目的重要操作，queue是解決最短路徑的利器，此處體現不多。
（勤加練習，勤寫博客）2020/1/18/21:28
