原题链接：3.岛屿个数 - 蓝桥云课 (lanqiao.cn)
感觉这个题出的真的特别好，考察了对bfs的使用，包括连通性的一系列判断，如果对bfs掌握的不熟练真的很难想出如何下手来做这道题。
这里我们需要用海水来进行bfs，海水可以渗透，也就是说可以走8个方向，因为我们要从任意一个边界点出发，所以我们需要把图扩展一下，变成n+2,m+2的图，我们把第0行第0列，和n+1行，n+1列变成0，也就是海水，这样的话我们从0，0开始遍历，就可以从每一个边界点进入判断，当然，我们的越界条件也要变成 n+2 ， 和 m+2（这里真的很重要www ， 博主刚开始做这道题，因为没有判别好边界问题导致直接全wa，要是这是在考场上这样，不得直接寄了，本来就不会几道），然后当我们第一次搜到一个岛屿的时候，他的初始状态是1，也就是说我们还没有搜索到过这个岛屿，这样的话我们就把最终答案 ans ++ ，然后对这个岛屿进行染色，染色当然很简单，就是一个判定连通性的问题，把这个1联通的所有1都变成2 ，这样就表示我们已经搜过这个岛屿了，如果这个岛屿内部也有岛屿，而且外面这个岛屿是封闭的我们的外界海水就渗透不进去，那我们就不会搜索到子岛屿，子岛屿也就不会参与计数；
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std ;
const int N = 100 ;
int d1[4][2] = {{0,1},{0,-1},{1,0},{-1,0}} ;
int d2[8][2] = {{0,1},{0,-1},{1,0},{-1,0},{1,1},{-1,1},{1,-1},{-1,-1}} ;
struct node{//这是我们记录搜索到的点的坐标
int x , y;
node(int xx ,int yy){
x = xx , y = yy ;
}
bool operator < (const node & o) const {
if(x == o.x) return y < o.y ;
else return x < o.x ;
}
};
queue<node> q ;//用于bfs
char mp[N][N] ;//存图
int n , m ;
int ans ;//返回值
void dfs(int x, int y){//染色，判断岛屿的上下左右四个方向，如果有陆地的话，索命他们是联通的，就对他们进行染色
mp[x][y] = '2' ;
for(int i = 0 ; i < 4 ; i ++){
int tx = x + d1[i][0] , ty = y + d1[i][1] ;
if(mp[tx][ty] == '1'){
dfs(tx,ty) ;
}
}
}
void bfs1(){
q.push(node(0,0)) ;
while(!q.empty()){
node now = q.front() ;
q.pop() ;
int x = now.x , y = now.y ;
for(int i = 0 ; i < 8 ; i ++){
int tx = x + d2[i][0] , ty = y + d2[i][1] ;
if(tx<0||tx>n+1||ty<0||ty>m+1||mp[tx][ty] == '2') continue ;//越界或者已经搜索过了
if(mp[tx][ty] == '1'){
ans ++ ; dfs(tx,ty) ;//如果碰到新的陆地就进行染色
}
if(mp[tx][ty] == '0'){//如果是海水，就进入队列让下一个海水继续渗透
mp[tx][ty] = '2' ;
q.push(node(tx,ty)) ;
}
}
}
}
int main(){
int t ; cin >> t ;
while(t --){
ans = 0 ;
memset(mp,'0',sizeof(mp));
cin >> n >> m ;
for(int i = 0 ; i <= n ; i++) mp[i][0] = '0' ;//对边界进行初始化，保证从所有边界点的海水进行渗透
for(int j = 0 ; j <= m ; j++) mp[0][j] = '0' ;
for(int i = 1 ; i <= n ; i ++){
for(int j = 1 ; j <= m ; j ++){
cin >> mp[i][j] ;
}
}
bfs1() ;
cout << ans << endl ;
}
}