$BFS$
$bfs$特点
一般在边权相同的图中使用$bfs$算法, 相比$dfs$有如下特点:
-
逐层遍历, 第一次遇到的状态即是离初始最近的状态 — “最小”步数.
-
基于迭代, 没有“爆栈”风险.
$Flood\;Fill$
洪水填充算法, 正如名字所说, 算法从图中某个“凹地”开始, 向四周凹地扩展, 直到周围所有凹地全被填充.
算法效果: 可在图中通过线性时间找到某点所在联通块所有顶点.
$Flood\;Fill$可用$bfs$也可用其他算法如$dfs$实现.
具体实现
-
题目求联通块数目, 使用$bfs$实现$Flood\;Fill$算法.
-
联通分为
4
联通和8
联通, 本题属于8
联通. -
访问过的顶点需要标记, 标记可分为出队时标记或入队时标记, 一般采用入队时标记,
防止重复入队从而增加运行时间. -
因为每个点
W
只会被入队一次, 所以可以将入队顶点对应值修改为.
, 达到标记效果.
具体代码
#include <iostream>
#define x first
#define y second
using namespace std;
typedef pair<int, int> pii;
const int N = 1010;
int n, m;
char g[N][N];
pii q[N * N];
void bfs(int sx, int sy)
{
int hh = 0, tt = 0;
q[tt ++] = {sx, sy};
g[sx][sy] = '.';
while( hh < tt )
{
pii cur = q[hh ++];
int x = cur.x, y = cur.y;
for( int nx = x - 1; nx <= x + 1; nx ++ )
for( int ny = y - 1; ny <= y + 1; ny ++ )
{
if( nx < 0 || nx >= n || ny < 0 || ny >= m ) continue;
if( g[nx][ny] == '.' ) continue;
g[nx][ny] = '.';
q[tt ++] = {nx, ny};
}
}
}
int main()
{
cin >> n >> m;
for( int i = 0; i < n; i ++ ) cin >> g[i];
int res = 0;
for( int i = 0; i < n; i ++ )
for( int j = 0; j < m; j ++ )
if( g[i][j] == 'W' )
{
bfs(i, j);
res ++;
}
cout << res << endl;
return 0;
}