题目描述

要注意判重(st数组)

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

const int N=1010;
char w[N][N];
int st[N][N];
typedef pair<int, int> PII;
int n,m;


int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>w[i][j];
        }
    }
    queue<PII> q;
    int res=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            //是W且没被遍历到
            if(w[i][j]=='W' && st[i][j]==0)
            {
                q.push({i,j});
                res++;
                st[i][j]=res;
                int dx[]={1,0,-1,0,1,1,-1,-1};
                int dy[]={0,1,0,-1,1,-1,-1,1};
                while(q.size())
                {
                    auto t=q.front();
                    q.pop();
                    for(int k=0;k<8;k++)
                    {
                        int a=t.first+dx[k];
                        int b=t.second+dy[k];
                        if(a>=1 && a<=n &&b>=1 &&b<=m &&w[a][b]=='W' && st[a][b]==0)
                        {
                            st[a][b]=res;
                            q.push({a,b});
                        }
                    }
                }
                //break;
            }
        }
    }


    cout<<res;



    return 0;



}

二刷，思路更清晰一点，此题的步骤为

1. 遍历到每个w
2. 遍历到了，cnt++，做一次dfs，把相邻的所有w标记

bfs的思路为

入队的时候标记！！
然后判断相邻点满足条件的时候标记

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

typedef pair<int,int> pii;
const int N=1010;
char w[N][N];
int st[N][N];
queue<pii> q;

int dx[]={0,1,1,1,0,-1,-1,-1};
int dy[]={1,1,0,-1,-1,-1,0,1};
int n,m;

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>w[i][j];
        }
    }
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(w[i][j]=='W'&&st[i][j]==0)
            {
                q.push({i,j});
                st[i][j]=1;
                cnt++;
                while(q.size())
                {
                    auto t=q.front();
                    int x=t.first;
                    int y=t.second;
                    q.pop();
                    for(int i=0;i<8;i++)
                    {
                        for(int j=0;j<8;j++)
                        {
                            int a=x+dx[i];
                            int b=y+dy[i];
                            if(a<=n&&b<=m&&st[a][b]==0&&w[a][b]=='W')
                            {
                                q.push({a,b});
                                st[a][b]=1;
                            }
                        }
                    }
                }
            }
        }
    }
    cout<<cnt;

    return 0;
}

2023/12/1

经典BFS
没复习，成功AC了

#include <iostream>
#include <cstring>
#include <queue>
#include <vector>

using namespace std;

const int N=1010;
char g[N][N];
// 表示当前是否被标记
int st[N][N];

int dx[]={0,1,1,1,0,-1,-1,-1};
int dy[]={1,1,0,-1,-1,-1,0,1};
int n,m;
typedef pair<int ,int> pii;

queue<pii> q;

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>g[i][j];
        }
    }

    int res = 0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            // 如果该位置为w,且还没有被遍历过，以它为起点遍历
            if(g[i][j] =='W' && st[i][j] == 0)
            {
                q.push({i,j});
                st[i][j] = 1;
                // res+1
                res++;
                while(q.size())
                {
                    auto t = q.front();
                    int x = t.first;
                    int y = t.second;

                    q.pop();
                    // 朝8个方向走
                    for(int k=0;k<8;k++)
                    {
                        int nx = x+dx[k];
                        int ny = y+dy[k];

                        // if(nx<=0 || ny<=0 || nx>=n || ny>=m)
                        // continue;

                        // if(st[nx][ny])
                        // continue;

                        if(nx>=1 && ny>=1 && nx<=n && ny<=m && st[nx][ny]==0 && g[nx][ny] =='W')
                        {
                            q.push({nx, ny});
                            st[nx][ny] = 1;
                        }

                    }
                }
            }
        }
    }
    cout<<res;



    return 0;
}