題目地址

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=838&page=show_problem&problem=513

題目分析

就是搜索一個二維數組里面的'@'聯通集，并求聯通集的個數，做法是：用二維數組存儲輸入的字符，然后找dfs()的第一個起點，因為不是有向圖所以可以從二維數組的第一個'@'開始進行dfs()搜索。dfs()的寫法就是遞歸，因為要求遞歸找到對應起點的所有子孫并標上序號，所以還需要一個idx[][]去存儲每個'@'的所屬連通集序號。dfs()寫法中遞歸的條件也是需要注意的，具體的要求是：

• 點在二維數組范圍內
• 點沒有被標號為某個聯通集序號
• 點為'@'

代碼：

#include <bits/stdc++.h> using namespace std;const int maxn = 210; int m,n; char buf[maxn][maxn]; int idx[maxn][maxn];bool inside(int r,int c){if(r < 0 || r >= m || c < 0 || c >= n) return false;return true; } void dfs(int r,int c ,int id){idx[r][c] = id;for(int dr = -1;dr <= 1;dr++){for(int dc = -1;dc <= 1;dc++){if(dr != 0 || dc != 0){ //掃描的結點不是本身 if(inside(r+dr,c+dc) && idx[r+dr][c+dc] == 0 && buf[r+dr][c+dc] == '@') //周邊的結點滿足條件則遞歸：1：不越界，2：沒有被標號;3:為'@' dfs(r+dr,c+dc,id);}}} } int main(void){while(scanf("%d%d",&m,&n) == 2 && m && n){for(int i = 0;i < m;i++){scanf("%s",buf[i]);}memset(idx,0,sizeof(idx));int cnt = 0;for(int i = 0;i < m;i++){for(int j = 0;j < n;j++){if(buf[i][j] == '@' && idx[i][j] == 0)dfs(i,j,++cnt); //深度優先搜索 }}printf("%d\n",cnt);}return 0; }

補充一種和劉汝佳不同的做法，不需要存儲聯通塊的序號，更加簡單:

#include <bits/stdc++.h> using namespace std;const int maxn = 210; int m,n; char buf[maxn][maxn]; bool inside(int r,int c){if(r < 0 || r >= m || c < 0 || c >= n) return false;return true; }void dfs(int r,int c){buf[r][c] = '*'; //將遍歷過的所有連通塊全部變為*;就可以不用存儲連通塊序號的數組了//循環遍歷移動8個方向 for(int dr = -1;dr <= 1;dr++){for(int dc = -1;dc <= 1;dc++){//判斷(r+dr,c+dc)是不是在區域內，并且為油田 if(inside(r+dr,c+dc) && buf[r+dr][c+dc] == '@')dfs(r+dr,c+dc);}} }int main(void){while(scanf("%d%d",&m,&n) == 2 && m && n){for(int i = 0;i < m;i++){scanf("%s",buf[i]);}int cnt = 0;for(int i = 0;i < m;i++){for(int j = 0;j < n;j++){if(buf[i][j] == '@'){dfs(i,j); cnt++;}}}printf("%d\n",cnt);}return 0; }

轉載于:https://www.cnblogs.com/Western-Trail/p/9180795.html

總結

以上是生活随笔為你收集整理的Uva572(DFS+联通集)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。