原题链接：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 ; } }
