dfs

先遍历图，找到所有岛屿（包括子岛） 然后从外海开始八个方向查找岛，并计数

C++ 代码

#include<bits/stdc++.h>

using namespace std;

const int N=52;
int ct=1;
int ff=0;
bool flag=false;
int m=0;
int n=0;
int mp[N][N];
int rec[(N+1)*(N+1)];

//上右下左 
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
//八个方向 
int dx2[8]={-1,-1,0,1,1,1,0,-1};
int dy2[8]={0,1,1,1,0,-1,-1,-1};

//海水查找 
void bs(int x,int y)
{
    if(x>m+1||x<0||y<0||y>n+1)
    return;

    if(mp[x][y]!=0)
    {
        //第一次遇到 
        if(rec[mp[x][y]]==0&&mp[x][y]!=-1){
            rec[mp[x][y]]=1;
            ff++;
        }
        return ;        
    }

    mp[x][y]=-1;
    for(int i=0;i<8;i++){
        bs(x+dx2[i],y+dy2[i]);
    }    
}
//标记岛屿 
void dfs(int x,int y){
    if(x<1||x>m||y>n||y<1)
    return;
    if(mp[x][y]!=1)
    return;
    mp[x][y]=ct;
    for(int i=0;i<4;i++){
            dfs(x+dx[i],y+dy[i]);

    }   
}
int main(){
    int zu;
    cin>>zu;
    while(zu--){
        cin>>m>>n;
        memset(mp, 0, sizeof(mp));
        memset(rec,0, sizeof(rec));
        ff=0;
        ct=1;
        //输入地图 
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++)
            {
                char c; 
                cin >> c;
                mp[i][j]=c-'0';
            }
        }
        //每次遍历岛 
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++)
            if(mp[i][j]==1)
            {
                //ct表示岛的数量,为了和1区分，从2开始 
                ct++;
                dfs(i,j);  
            }
        }
        bs(0,0);    
        cout<<ff<<endl;
        memset(rec, 0, sizeof(rec));

    }   
    return 0; 
}