岛屿个数 bfs C语言解法 附详细注释

解题思路:若是统计全部岛屿的数目，这就是一道经典题目。虽然题目要求不统计环中的岛屿数目，但是我们只需要在原来的基础上判断一个岛屿是不是环就可以了。

                首先拿出岛屿问题通解，记录数组grid,确定访问状态数组visit，方向盘（这个题陆地和岛屿有独立方向盘，因为海水是可以通过东南/东北等斜度方向传导过去的，但是陆地就只能上下左右）,check方法（确保遍历时没有越界的元素），bfs方法或dfs方法。

                根据题目分析，我们可以挨个遍历未访问的元素，若是海水，就便历旁边的元素，若是陆地，就单独寻找陆地，把所有找到的连接的陆地标明为已访问，这样的话若陆地是环，每当遍历到环上的元素时都是已访问，就不会遍历到里面的岛屿。若不是环，海水就可以传导进去，找到里面的陆地。

注意事项:地图输入的每一行都是一行字符，不要用错接收方式

参考代码:代码较长，105行

#include <stdio.h>  //引入库函数 输入输出

#include <string.h>// 字符串与memset

#include <stdbool.h>//bool类型

#include <stdlib.h>//malloc

char grid[55][55]; //记录数组

bool visit[55][55]; //访问状态数组

int seax[8]={0,0,-1,1,1,1,-1,-1}; //海水方向盘

int seay[8]={1,-1,0,0,-1,1,1,-1};

int roadx[4]={0,0,-1,1}; //陆地方向盘

int roady[4]={1,-1,0,0};

bool check(int i,int j,int m,int n){ //check方法

if(i<0 || j<0 || i>=m || j>=n){

return false;

}

return true;

}

void bfs_road(int x,int y,int m,int n){ //bfs遍历陆地方法 与遍历海洋思路相同，不赘述

int quene[2555][2];

int first=0;

int rear=0;

visit[x][y]=true;

quene[rear][0]=x;

quene[rear][1]=y;

rear++;

while(first<rear){

int i=quene[first][0];

int j=quene[first][1];

first++;

for(int k=0;k<4;++k){

int ni=i+roadx[k];

int nj=j+roady[k];

if(check(ni,nj,m,n) && grid[ni][nj]=='1'  && visit[ni][nj]==false){

visit[ni][nj]=true;

quene[rear][0]=ni;

quene[rear][1]=nj;

rear++;

}

}

}

}

int bfs_sea(int x,int y,int m,int n,int ans){ //bfs遍历海洋方法

int quene[2555][2];  //C语言用数组模拟队列，根据变量范围确定数量大小

int first=0; //队列首

int rear=0;//队列尾

visit[x][y]=true;//将该点设为已访问过

quene[rear][0]=x;//将该点加入队列

quene[rear][1]=y;

rear++;//队列尾自增

while(first<rear){ //当队列中还有元素

int i=quene[first][0];//抽出目前的元素

int j=quene[first][1];

first++;//队列首自增

for(int k=0;k<8;++k){//调用方向盘找旁边的元素

int ni=i+seax[k];

int nj=j+seay[k];

if(check(ni,nj,m,n) && grid[ni][nj]=='0' && visit[ni][nj]==false ){//满足两大条件 且还是海

visit[ni][nj]=true;    //将该点设为已访问，加入队列继续寻找旁边的岛屿

quene[rear][0]=ni;

            quene[rear][1]=nj;

            rear++;

}

if(check(ni,nj,m,n) && grid[ni][nj]=='1' && visit[ni][nj]==false ){//满足两大条件 且是陆地

ans++; //找到岛屿了，数量+1

bfs_road(ni,nj,m,n);//用bfs访问整个岛屿，防止重复计算

}

}

}

return ans; //返回最终得出的岛屿数量

}

int main(){ //主方法

int T;   

scanf("%d",&T); //读入T

int *ans = (int*)malloc(sizeof(int)*T); //创造一个长度为T的数组，每个元素记录该组数据有几个岛屿

for(int k=0;k<T;++k){ //对T组数据进行一一判定

    int m,n;

    scanf("%d %d",&m,&n);  //读入行列

for(int i=0;i<m;++i){  //读入地图 

scanf("%s",&grid[i]);// 这里要注意输入的是字符串，看好类型

  }  

bool flag=false; //如果整个地图外围就是一个大环，全都是陆地，flag一直是false，会返回岛屿数目为1

    memset(visit,false,sizeof(visit)); //设定全图为未访问状态

    int anss=0; //定义岛屿数目变量为0

for(int i=0;i<m;++i){ //双重for循环遍历整个地图

for(int j=0;j<n;++j){

if(i==0 || i==m-1 || j==0 || j==n-1){ //先从外面边界遍历 防止遍历里面遍历到环的内部

if(visit[i][j]==false && grid[i][j]=='0' ){//如果找到了边界的海

flag=true;  //地图不是一个大环

anss=bfs_sea(i,j,m,n,anss);//调用dfs方法返回岛屿数目

}

}

}

}

if(flag==false){  //如果整个地图外围就是一个大环，会返回岛屿数目为1

anss=1;

}

ans[k]=anss;//记录该组数据岛屿数目

}  

for(int i=0;i<T;++i){ //分行输出存储的岛屿数目数组

printf("%d\n",ans[i]);

}

return 0; //返回值

}