题解：P9243 [蓝桥杯 2023 省 B] 岛屿个数

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
using ll=long long;
char mp[60][60];
int vis[60][60]; // 经典 dfs 标记
int sc; // 染色编号
int v[60][60]; // 在查找该岛屿能否走到外海的标记
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int dx1[]={1,1,1,0,0,-1,-1,-1};
int dy1[]={0,1,-1,1,-1,0,1,-1};
int n,m,ans;
void dfs(int x,int y){
	vis[x][y]=sc;
    for(int i=0;i<4;i++){ // 从上下左右遍历，将岛屿染色
		int nx=dx[i]+x;
		int ny=dy[i]+y;
		if(vis[nx][ny]||nx<1||nx>n||ny<1||ny>m||mp[nx][ny]=='0')continue;
		dfs(nx,ny);
	}
} 
bool query(int x,int y){
	if(x>n||x<1||y>m||y<1)return 1;
	v[x][y]=1;
	for(int i=0;i<8;i++){ // 观察是否能走到外海要从四面八方遍历
		int nx=dx1[i]+x;
		int ny=dy1[i]+y;
		if((mp[nx][ny]=='1'&&vis[nx][ny]!=sc)||v[nx][ny])continue; // 要沿着海域走，不能走到其他岛屿上，但是可以在本岛领土走
		if(query(nx,ny))return 1;
	}
	return 0;
}
void solve(){
    cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>mp[i][j];
			vis[i][j]=0;
		}
	}
	ans=0; // 全局变量 ans 归零
	sc=0; // 编号归零
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(vis[i][j]||mp[i][j]=='0')continue;
			sc++;
			dfs(i,j);
			for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)v[i][j]=0; // 将v标记全部还原为 0
			if(query(i,j))ans++; // 如果能走到外海就说明不是子岛屿
		}
	}
	cout<<ans<<endl;
}
int main() {
	ios::sync_with_stdio(false);                                                                       
	cin.tie(nullptr);
	int t=1;cin>>t;
	while(t--)solve();
	
}