注意搜索时条件判断里的边界问题!!!

AcWing 残垣断壁

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=110;
int n,m;
char g[N][N];
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

int dfs(int x,int y)
{
    g[x][y]='.';
    for(int i=0;i<4;i++)
    {
        int a=x+dx[i],b=y+dy[i];
        if(a>=0&&a<n&&b>=0&&b<m&&g[a][b]=='B')
        dfs(a,b);
    }
}

void bfs(int x,int y)
{
    g[x][y]='.';
    queue<PII> q;
    q.push({x,y});
    while(!q.empty())
    {
        auto t=q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {
            int a=t.first+dx[i],b=t.second+dy[i];
            if(a>=0&&a<n&&b>=0&&b<m&&g[a][b]=='B')
            {
                q.push({a,b});
                g[a][b]='.';
            }
        }
    }
}

int main()
{
    int res=0;
    cin>>n>>m;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
        cin>>g[i][j];//先读入地图 

    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            if(g[i][j]=='B')//再遍历地图寻找起点位置 
            {
                g[i][j]='.';
                dfs(i,j);//做连通
                res++;//统计连通块的数量
            }
        cout<<res<<endl;
        return 0;
} 

AcWing 红与黑

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=25;
int n,m;
char g[N][N];
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

int bfs(int x,int y)
{
    queue<PII> q;
    q.push({x,y}); g[x][y]='#';
    int res=0;//记录连通块内部点的数量(不能用全局变量)

    while(!q.empty())
    {
        auto t=q.front();
        q.pop();
        res++;//每次弹出队列(说明搜到一个点)就增加
        for(int i=0;i<4;i++)
        {
            int a=t.first+dx[i],b=t.second+dy[i];
            if(a>=0&&a<n&&b>=0&&b<m&&g[a][b]=='.')
            {
                g[a][b]='#';
                q.push({a,b});
            }
        }
    }

    return res;
}

int dfs(int x,int y)
{
    int res=1;//记录连通块内部点的数量(不能用全局变量)
    g[x][y]='#';
    for(int i=0;i<4;i++)
    {
        int a=x+dx[i],b=y+dy[i];
        if(a>=0&&a<n&&b>=0&&b<m&&g[a][b]=='.')
        res+=dfs(a,b);
    }
    return res;
}

int main()
{
    while(cin>>m>>n,n||m)//输入数据当读入两个0时结束
    {
        for(int i=0;i<n;i++) cin>>g[i];

        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                if(g[i][j]=='@')//确定起点
            cout<<bfs(i,j)<<endl;
    }
    return 0;
}

洛谷 填涂颜色

#include<bits/stdc++.h>
using namespace std;
const int N=40;

int n;
int g[N][N];
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

void dfs(int x,int y)
{
    g[x][y]=2;
    for(int i=0;i<4;i++)
    {
        int a=x+dx[i],b=y+dy[i];
//在先搜索的时候应该搜索到矩阵的外面一圈(0,n-1)否则的话就会出现错误(边缘处被涂色)
        if(a>=0&&a<=n+1&&b>=0&&b<=n+1&&g[a][b]==0)//注意边界问题 
        {
            g[a][b]=2;
            dfs(a,b);
        }
    }
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>g[i][j];
        dfs(0,0);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(g[i][j]==0) cout<<2<<" ";
            if(g[i][j]==1) cout<<1<<" ";
            if(g[i][j]==2) cout<<0<<" ";    
        }
        cout<<endl;
    }
} 

洛谷 拯救总部

#include<bits/stdc++.h>
using namespace std;
const int N=550;

char ch;
int g[N][N];
int n,m,res=0;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

void dfs(int x,int y)
{
    for(int i=0;i<4;i++)
    {
        int a=x+dx[i],b=y+dy[i];
        if(a>=0&&a<=n+1&&b>=0&&b<=m+1&&g[a][b]==0)
        {
            g[a][b]=2;//围墙外的(即洪水可泛滥的)都标记上
            dfs(a,b);
        }
    }
}

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

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            cin>>ch;
            if(ch=='0') g[i][j]=0;//0表示总部,1表示围墙 
            else g[i][j]=1;//处理成数字地图('*'换成'1')
        }
    dfs(0,0);//从第一个点开始搜索
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(g[i][j]==0)//还是0的就说明没有被洪水泛滥到(因为被围住了搜索不到)
            res++;
            cout<<res;//没被洪水淹没的总部 
        return 0;
}

蓝桥杯 全球变暖

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=1010;

int n,cnt=0;
char g[N][N];
bool st[N][N];
bool flag;//标记,true表示不会被淹没的高地 
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

void dfs(int x,int y)
{
        st[x][y]=true;
        for(int i=0;i<4;i++)
        {
            int a=x+dx[i],b=y+dy[i];
            if(st[a][b]==false&&g[a][b]=='#')
            {
                st[a][b]=true;
                dfs(a,b);
            }
            //判断是否为高地 
            if(g[x+1][y]=='#'&&g[x-1][y]=='#'&&g[x][y+1]=='#'&&g[x][y-1]=='#')
            flag=true;//不会被淹没 
        }   
} 

void bfs(int x,int y)
{
    queue<PII> q;
    q.push({x,y}); st[x][y]=true;

    while(!q.empty())
    {
        auto t=q.front();
        q.pop();
        //判断是否为高地 
        if(g[t.first+1][t.second]=='#'&&g[t.first-1][t.second]=='#'&&g[t.first][t.second+1]=='#'&&g[t.first][t.second-1]=='#')
            flag=true;//不会被淹没 
        for(int i=0;i<4;i++)
        {
            int a=t.first+dx[i],b=t.second+dy[i];
            if(st[a][b]==false&&g[a][b]=='#')
            {
                q.push({a,b});
                st[a][b]=true;
            }
        }
    }
}

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        cin>>g[i][j];
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            if(st[i][j]==false&&g[i][j]=='#')
            {
                flag=false;
                dfs(i,j);//将陆地连通并且判断了该岛屿是否有高地 
                if(flag==false) cnt++;//会被淹没 
            }
    cout<<cnt<<endl;
    return 0;
}