• • 題目：
    • 分析與解答

題目：

多組案例，每組案例輸入一個(gè)m行n列的字符矩陣，統(tǒng)計(jì)字符‘@’組成多少個(gè)連通塊。如果兩個(gè)字符‘@’所在的格子相鄰（橫、豎或?qū)蔷€），則說(shuō)明它們屬于同一連通塊。

Sample Input

1 1*3 5*@*@***@***@*@*1 8@@****@*5 5****@*@@*@*@**@@@@*@@@**@0 0

Sample Output

0122

分析與解答

1.找到油田，然后通過(guò)循環(huán)遍歷他周圍的八個(gè)位置，不斷調(diào)用dfs函數(shù)，如果連通，則講連通分量標(biāo)號(hào)
2.循環(huán)，找沒(méi)標(biāo)記過(guò)的油田，然后繼續(xù)進(jìn)行1，標(biāo)號(hào)增加
3.油田均已標(biāo)記完，此時(shí)輸出標(biāo)號(hào)，就是連通塊個(gè)數(shù)

怎么寫bfs：
結(jié)束遞歸的條件有兩個(gè)，一個(gè)是超過(guò)了格子的范圍，另一個(gè)是之前曾經(jīng)出現(xiàn)過(guò)，以及這個(gè)格子不是油田。找的話每個(gè)油田做標(biāo)號(hào)，是同一聯(lián)通區(qū)域的標(biāo)上一樣的號(hào)，最后輸出最終的標(biāo)號(hào)即可。調(diào)用時(shí)機(jī)：if(idx[i][j]==0&&pic[i][j]==’@’)這個(gè)數(shù)沒(méi)標(biāo)記過(guò)，而且屬于油田。bfs里面用兩個(gè)for循環(huán)直接把他八個(gè)方向都掃描了一遍，并且如果滿足條件就進(jìn)行初始化，此時(shí)如果在同一個(gè)連通區(qū)域他們的值是相同的，所以main里調(diào)用bfs時(shí)一定是發(fā)現(xiàn)了不同的連通區(qū)域，如果要求不同連通區(qū)域個(gè)數(shù)，就只用在main里面更改cnt的個(gè)數(shù)

#include<cstdio> #include<cstring> using namespace std; const int maxn = 100+5; char pic[maxn][maxn]; int m,n,idx[maxn][maxn];void DFS(int r,int c,int id) {if(r<0||r>=m||c<0||c>=n) return ;if(idx[r][c]>0||pic[r][c]!='@') return ;idx[r][c]=id;for(int dr=-1;dr<=1;dr++)for(int dc=-1;dc<=1;dc++)if(dr!=0||dc!=0)DFS(r+dr,c+dc,id); } int main() {while(scanf("%d%d",&m,&n)!=EOF&&m&&n){for(int i=0;i<m;i++) scanf("%s",pic[i]);memset(idx,0,sizeof(idx));int cnt=0;for(int i=0;i<m;i++)for(int j=0;j<n;j++)if(idx[i][j]==0&&pic[i][j]=='@')DFS(i,j,++cnt);printf("%d\n",cnt);}return 0; }

也可以寫八條DFS調(diào)用

#include<cstdio> #include <cstring> using namespace std; #define maxn 105 char a[maxn][maxn]; bool vis[maxn][maxn]; int n,m; void DFS(int x,int y) {if(x<0||x>=n||y<0||y>=m) return ;if(a[x][y]=='*'||vis[x][y]) return;vis[x][y]=true;DFS(x+1,y+1);DFS(x+1,y);DFS(x+1,y-1);DFS(x,y-1);DFS(x-1,y-1);DFS(x-1,y);DFS(x-1,y+1);DFS(x,y+1); } int main() {while(scanf("%d%d",&n,&m)!=EOF){if(n+m==0) break;for(int i=0; i<n; i++)scanf("%s",a[i]);int sum=0;memset(vis,false,sizeof(vis));for(int i=0; i<n; i++)for(int j=0; j<m; j++)if(!vis[i][j]&&a[i][j]=='@'){DFS(i,j);sum++;}printf("%d\n",sum);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的DFS实现floodfill算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。