$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

两种思路任你选择！

思路1：bfs

1. 枚举所有点，符合条件就加入队列并记录该点
2. 取出队头，枚举该点的八个方向，符合条件的加入队列并记录该点
3. cnt 表示连通块个数，bfs() 调用几次就说明有多少个连通块

完整代码1

#include<bits/stdc++.h>

using namespace std;

#define x first
#define y second

typedef pair<int,int> PII;

const int N = 1010;

int n,m;
char g[N][N];
bool st[N][N];
queue<PII> q;

void bfs(int sx,int sy)
{
    //加入队列并记录该点
    q.push({sx,sy});
    st[sx][sy]=true;

    while(q.size())
    {
        //取出队头
        auto t=q.front();
        q.pop();

        //枚举八个方向
        for(int i=t.x-1;i<=t.x+1;i++)
            for(int j=t.y-1;j<=t.y+1;j++)
            {
                if(i==t.x&&j==t.y) continue;
                if(i<0||i>=n||j<0||j>=m) continue;
                if(g[i][j]=='.'||st[i][j]) continue;

                //将该点放入队列并记录该点
                q.push({i,j});
                st[i][j]=true;
            }
    }
}

int main()
{
    cin>>n>>m;

    for(int i=0;i<n;i++) cin>>g[i];

    //连通块个数
    int cnt=0;

    //枚举所有点
    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);
                cnt++;
            }

    cout<<cnt<<endl;

    return 0;
}

思路2：dfs

1. 枚举所有点，符合条件就 dfs 该点
2. 将该点变成其他不符合条件的符号，这样就不用st数组来记录了
3. 枚举八个方向，符合条件的点就直接 dfs
4. cnt 表示连通块个数，dfs() 调用几次就说明有多少个连通块

完整代码2

#include<bits/stdc++.h>

using namespace std;

const int N = 1010;

int n,m;
char g[N][N];

//用数组来存储八个方向
int dx[8]={-1,-1,-1,0,0,1,1,1},dy[8]={-1,0,1,-1,1,-1,0,1};

void dfs(int x,int y)
{
    //一种巧妙的方法，这样就不同st数组来记录了
    g[x][y]='.';

    //枚举八个方向
    for(int i=0;i<8;i++)
        if(g[x+dx[i]][y+dy[i]]=='W')
            dfs(x+dx[i],y+dy[i]);
}

int main()
{
    cin>>n>>m;

    for(int i=0;i<n;i++) cin>>g[i];


    //记录连通块个数
    int cnt=0;

    //枚举所有点
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            if(g[i][j]=='W')
            {
                dfs(i,j);
                cnt++;
            }

    cout<<cnt<<endl;

    return 0;
}