岛屿个数：

 

分析： 

题目要求我们求地图上有多少个”外岛屿“， 从样例数据上可以知道，我们要从地图边缘一圈的”海“

点开始 BFS 。 如果要求外岛屿的话， 从地方中间的”海“点开始 BFS 是不行的，这样的结构是找不到”外岛屿“， 只能找到”内岛屿“。

从地图上外围一圈”海“这个点开始 BFS， 先把这个点标记一下， 防止重复访问这个点。当访问到”1“ ，也就是陆地的时候，在从陆地这个点开始 DFS/BFS ，开始前要将这个”陆地点“标记一下， 避免被重复访问，最后和这个”陆地点“相连的陆地全部被访问， 可以确定这是个外岛屿，数量 +1。

 

 

 代码 BFS+BFS标记陆地：

 

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

#define x first
#define y second
typedef pair<int, int> PII;

int t, n, m, ans;
char g[N][N]; //地图 
bool st_sea[N][N], st_lu[N][N];// 避免重复
queue<PII> q, l;

//海水的向量坐标
int dx1[] = {1, 1, 0, -1, -1, -1, 0, 1};
int dy1[] = {0, 1, 1, 1, 0, -1, -1, -1};
//陆地的向量坐标
int dx2[] = {-1, 0, 1, 0};
int dy2[] = {0, 1, 0, -1};

void bfs_lu(int x1, int y1){
    l.push({x1, y1}); // 存入队列
    
    while(l.size()){
        //取出
        auto t = l.front();
        l.pop();
        
        for(int i=0; i<4; i++){
            //四个方向
            int a = dx2[i] + t.x, b = dy2[i] + t.y;
            //避免越界问题
            if(a<1 || a>n || b<1 || b>m)continue;
            //避免访问到“海”
            if(g[a][b] =='0')continue;
            if(g[a][b] == '1' && !st_lu[a][b]){
                st_lu[a][b] = true;
                l.push({a, b});
            }
        }
    }
}

void bfs_sea(int x1, int y1){
    q.push({x1, y1}); //将坐标存入队列
    
    while(q.size()){
        // 将队列中的坐标取出
        auto t = q.front(); 
        q.pop();
        
        for(int i = 0; i< 8; i++){
            //八个方向
            int a = dx1[i] + t.x,  b = dy1[i] + t.y;
            //避免越界问题
            if(a<1 || a>n || b<1 || b>m)continue;
            //当访问到“1” 陆地时，开始DFS/BFS，将这一片陆地标记，然后ans+1
            if(g[a][b] == '1' && !st_lu[a][b]){
                st_lu[a][b] = true;
                bfs_lu(a, b);
                ans += 1;
            }
            if(g[a][b] == '0' && !st_sea[a][b]){
                st_sea[a][b] = true;
                q.push({a, b});
            }
        }
    }
}

int main(){
    cin >> t;
    
    while(t--){
        cin >> n >> m;
        //存入地图
        for(int i = 1; i <= n; i++){
            scanf("%s", g[i] + 1); 
        }
        //每次循环最终答案初始化0
        ans = 0; 
        //每次循环都要初始化  
        memset(st_sea, false, sizeof st_sea);
        memset(st_lu, false, sizeof st_lu);
        //从地图边缘一圈的海水开始 BFS
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                if(i==1 || i==n || j==1 || j==m){
                    if(g[i][j] == '0' && !st_sea[i][j]){
                        //访问过的点（海水） 在 st_sea 数组中标记为 true
                        //避免重复访问
                        st_sea[i][j] = true;
                        bfs_sea(i, j);
                    }
                }
            }
        }
        
        printf("%d\n", ans);
    }
    
    return 0;
}

数组模拟队列+DFS标记陆地： 

 

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

#define x first
#define y second
typedef pair<int, int> PII;

int t, n, m, ans;
char g[N][N]; //地图
bool st_sea[N][N], st_lu[N][N];//避免重复访问一个点
PII q[N*N]; //数组模拟队列

//海水的方向向量坐标
int dx1[] = {1, 1, 0, -1, -1, -1, 0, 1};
int dy1[] = {0, 1, 1, 1, 0, -1, -1, -1};
//陆地的方向向量坐标
int dx2[] = {-1, 0, 1, 0};
int dy2[] = {0, 1, 0, -1};

void dfs(int x1, int y1){
    
    for(int i = 0; i <4; i++){
        int a = dx2[i] + x1, b = dy2[i] + y1;
        
        //避免访问地图越界
        if(a<1 || a>n || b<1 || b>m)continue;
        if(g[a][b] == '0')continue;
        if(g[a][b] == '1' && !st_lu[a][b]){
            st_lu[a][b] = true;
            dfs(a, b);
        }
    }
}

void bfs(int x1, int y1){
    q[0] = {x1, y1}; //往数组中存入坐标
    int hh = 0, tt = 0; //队头 队尾
    
    while(hh <= tt){
        auto t = q[hh++]; //从数组中取出队头的坐标 然后队头 hh+1
        
        for(int i =0; i< 8; i++){
            int a = dx1[i]+t.x, b = dy1[i]+ t.y;
            
            //避免访问越界了
            if(a<1 || a>n || b<1 || b>m)continue;
            //当访问到 ‘1’ 的时候， 并且这个‘1’ 没有被访问过
            //开始 DFS ，将这个点标记， 答案 +1
            if(g[a][b] == '1' && !st_lu[a][b]){
                st_lu[a][b] = true;
                ans ++;
                dfs(a, b);
                
            }
            //当访问到‘0’时，并且这个‘0’没有被访问过
            //将这个‘0’坐标添加到数组中 再将这个点标记
            if(g[a][b] == '0' && !st_sea[a][b]){
                st_sea[a][b] = true;
                q[++tt] = {a, b};
            }
        }
    }
}

int main(){
    cin >> t;
    
    while(t--){
        cin >> n>> m;
        for(int i = 1; i <= n; i++){
            scanf("%s", g[i] + 1);
        }
        //初始化
        memset(st_sea, false, sizeof st_sea);
        memset(st_lu, false, sizeof st_lu);
        ans = 0;
        //从地图边缘的海开始BFS
        for(int i = 1; i<= n; i++){
            for(int j = 1; j<= m; j++){
                //访问地图边缘一圈
                if(i==1 || i==n || j==1 || j==m){
                    if(g[i][j] == '0' && !st_sea[i][j]){
                        //访问过要标记 防止重复
                        st_sea[i][j] = true;
                        bfs(i, j);
                    }
                }
            }
        }
        
        printf("%d\n", ans);
    }
    
    return 0;
}

总结：从地图边缘的”海“点开始 BFS， 这样确定开始访问到的陆地一定不是内岛屿。从这个点开是 BFS 访问到的第一个”陆地“点，在开始 BFS/DFS ，将这一片陆地标记。 然后 再将”海“点添加到队列中，继续访问没有标记过的”陆地“点，在从这个点 BFS/DFS， 标记一片陆地。