岛屿个数--bfs+dfs--注释易懂

解题思路:
要统计不包含子岛屿(外岛)的数量，选择从外到内去找岛屿
从四条边的海区(0)去找 ,当他的 8个方向(上下左右、左上、右上、左下、右下) 都是岛屿
时，那这些小岛就组成了一个大的岛 当其中一个方向是海时，那这些岛屿就没有全部相连组成了一个大的岛
遍历四条边，找到一个海为着点，向8个方向进行探索，探到陆地时，通过dfs将与他相连的岛屿全部
标记(v[i][j]=true) ,防止后续重复计入探索到海时就继续深入注意事项:

参考代码:

#include<bits/stdc++.h>
using namespace std;
const int N = 50+10;
string a[N];//地图 
bool v[N][N];//标记是否访问 
int s,w,ans=0;//s,w地图大小 
int lx[]={1,0,-1,0};//4个方向向量 
int ly[]={0,-1,0,1};//lx,ly为岛屿探索4个方向 
int hx[]={1,0,-1,0,1,1,-1,-1} ;//hx,hy为海的8个方向 
int hy[]={0,-1,0,1,-1,1,1,-1};
bool check(int x,int y);//检查数组下标是否合理 
void bfs (int x,int y);
void dfs(int x,int y) ;

void bfs(int x,int y){
	if(!check(x,y)) return;//下标不合理 
	v[x][y]=true;	//标记访问 
	for(int i=0;i<8;i++){//8个方向依次探索 
		if(check(x+hx[i],y+hy[i])&&!v[x+hx[i]][y+hy[i]]){//可以访问的下一块区域 
			if(a[x+hx[i]][y+hy[i]]=='1') {//下一块区域 是岛屿 
				dfs(x+hx[i],y+hy[i]);//先标记所有与他相连的岛屿 
				ans++;//岛屿数量加1 
			}
			else {
				bfs(x+hx[i],y+hy[i]);//下一块区域 是海，深入探索 
			}
		}
	}	
}

void dfs(int x,int y){
	if(!check(x,y)) return ;//下标不合理 
	v[x][y] = true; 	//标记访问
	for(int i=0;i<4;i++){//4个方向依次探索 
		//可以访问该方向的岛屿 
		if(check(x+lx[i],y+ly[i])&&a[x+lx[i]][y+ly[i]]=='1'&&!v[x+lx[i]][y+ly[i]]){			
			dfs(x+lx[i],y+ly[i]);//继续寻找相连岛屿 
		}
	}
}

bool check(int x,int y){ 
	return (x>=0&&x<s&&y>=0&&y<w);
}

void solve(){//读取数据 
	memset(v,false,sizeof(v));//初始或重置标记数组 
	cin>>s>>w;
	for(int i=0;i<s;i++){
		cin>>a[i];
	}
	//寻找4边的海域作为着点，注意循环条件不要重复顶点 
	for(int i=0;i<w;i++){
		if(a[0][i]=='0') {
			bfs(0,i);
		}
		if(a[s-1][i]=='0'){
			bfs(s-1,i);
		}
	}
	for(int i=1;i<s-1;i++){
		if(a[i][0]=='0') {
			bfs(i,0);
		}
		if(a[i][w-1]=='0'){
			bfs(i,w-1);
		}
	}	
	cout<<ans<<endl;
	ans =  0;
}

int main()
{
	int t=1;
	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}