Flood fill 算法簡介：

像洪水一樣，一圈一圈往外蔓延，像bfs。

flood fill 算法可以在線性復(fù)雜度內(nèi)，找到某個點所在的連通塊。

題目分析

來源：acwing

ac代碼

#include<bits/stdc++.h> using namespace std; #define x first #define y secondtypedef pair<int, int> PII;const int N = 1010, M = N * N; int n, m; char g[N][N]; PII q[M]; // bfs用的隊列：數(shù)組模擬隊列 bool st[N][N]; // 某點是否遍歷過// 數(shù)組模擬隊列 void bfs(int sx, int sy){int hh = 0, tt = 0;q[0] = {sx, sy};st[sx][sy] = true;while( hh <= tt){ // 隊列不空時PII t = q[hh ++];// 遍歷周圍8個相鄰點for(int i = t.x -1 ; i <= t.x + 1; i++)for(int j = t.y -1; j <= t.y +1; j ++){// 當(dāng)前點跳過if(i == t.x && j == t.y) continue;//位置不合法跳過if( i < 0 || i >= n || j <0 || j >= m) continue;// 不是水，跳過； 或者已經(jīng)遍歷過，跳過if(g[i][j] == '.' || st[i][j]) continue;// 該點壓入隊列，并標(biāo)記為遍歷過q[++ tt] = {i ,j};st[i][j] = true;}} }int main(){scanf("%d%d",&n, &m);// 讀入1行沒有空格，當(dāng)作字符串來讀for(int i = 0; i < n; i++) scanf("%s", g[i]);int cnt = 0; // 統(tǒng)計連通塊的個數(shù)for(int i = 0; i < n; i++)for( int j = 0; j < m; j ++)if( g[i][j] == 'W' && !st[i][j]){bfs(i, j); // 以(i,j)為起點進(jìn)行bfscnt ++;}cout << cnt << endl; }

題目來源

https://www.acwing.com/problem/content/1099/

總結(jié)

以上是生活随笔為你收集整理的算法提高课-搜索-Flood fill算法-AcWing 1097. 池塘计数:flood fill、bfs的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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