中矿新生赛 H 璐神看岛屿【BFS/DFS求联通块/连通块区域在边界则此连通块无效】

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

璐神现在有张n*m大小的地图，地图上标明了陆地（用"#"表示）和海洋（用"."表示），现在璐神要计算这张地图上岛屿的数量。

已知岛屿是由陆地的连通块组成，即一块陆地的上、下、左、右，左上，右上，左下，右下有其他陆地，则构成连通块，以此类推。

此外，岛屿的详细定义如下：

1、岛屿的周围必须全是海洋。

2、如果连通块有任意区域在地图边界，则该连通块不是岛屿。

输入描述:

第1行输入两个整数n，m，代表地图的长和宽。
第2-n+1行，每行输入m个字符，字符为"#"表示陆地，为"."表示海洋。
数据保证：0<n,m≤200

输出描述:

输出一行整数，代表岛屿的数量。

示例1

输入

3 3

...

.#.

...

输出

说明

只有中间的1块陆地是岛屿，所以岛屿数=1

示例2

输入

3 3

#..

.#.

...

输出

说明

中间的连通块有区域在边界，所以不是岛屿，岛屿数=0。

【分析】：bfs 求解连通块，注意的是在求解过程中，如果出现连通块区域在边界，则记录此连通块无效，但仍需将 bfs 操作进行完。
【代码】：

#include <bits/stdc++.h>

using namespace std;

const int maxn = ;

char mp[][];

int vis[maxn][maxn]={};

int dir[][] ={{,},{,},{-,},{,-},{-,-},{-,},{,-},{,}};

int n,m,flag=;

void dfs(int x,int y)

{

    vis[x][y]=;

     if(x==||y==||x==n-||y==m-)

           flag=;

    for(int i=;i<;i++)

    {

        int tx=x+dir[i][];

        int ty=y+dir[i][];

        if(mp[tx][ty]=='#'&&tx>=&&ty>=)

        {

            mp[tx][ty]='.';

            dfs(tx,ty);

        }

    }

}

int main()

{

    int sum=;

    cin>>n>>m;

    for(int i=;i<n;i++)

        cin>>mp[i];

    for(int i=;i<n;i++)

    {

        for(int j=;j<m;j++)

        {

            if(mp[i][j]=='#')

            {

                flag=;

                dfs(i,j);

                if(flag==)

                    sum++;

            }

        }

    }

    cout<<sum<<endl;

    return ;

}

DFS

#include<bits/stdc++.h>

using namespace std;

const int maxn=;

char mp[maxn][maxn];

int vis[maxn][maxn];

const int dir[][]={{,},{-,},{,},{,-},{,},{,-},{-,},{-,-}};

int n,m,ans=;

void bfs(int x,int y){

    if(mp[x][y]=='.'){

        vis[x][y]=;

        return;

    }

    if(x==||y==||x==n-||y==m-){

        vis[x][y]=;

      //  return;

    }

    queue<pair<int,int> >q;

    q.push(make_pair(x,y));

    while(!q.empty()){

        int nowx=q.front().first;

        int nowy=q.front().second;

        if(nowx==||nowy==||nowx==n-||nowy==m-){

            vis[x][y]=;

            //return;

        }

        q.pop();

        for(int i=;i<;++i){

            int x1=nowx+dir[i][];

            int y1=nowy+dir[i][];

            if(vis[x1][y1]==&&mp[x1][y1]=='#'){

                vis[x1][y1]=;

                q.push(make_pair(x1,y1));

            }

        }

    }

}

int main(){

    while(cin>>n>>m){

        memset(mp,,sizeof(mp));

        memset(vis,false,sizeof(vis));

        ans=;

        for(int i=;i<n;++i)

            cin>>mp[i];

        for(int i=;i<n;++i){

            for(int j=;j<m;++j){

                if(!vis[i][j]){

                    vis[i][j]=;

                    bfs(i,j);

                    if(vis[i][j]==){

                        ans++;

                    }

                }

            }

        }

        cout<<ans<<endl;

    }

    return ;

}

BFS

巴特西

中矿新生赛 H 璐神看岛屿【BFS/DFS求联通块/连通块区域在边界则此连通块无效】

题目描述

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

最新文章

热门文章