全球变暖-bfs

1.不沉的就是4个方向没有海，一个大岛屿有一个不沉就行了，其余染色就好了

2.第一个bfs来统计总岛屿个数

3.第二个来统计不沉岛屿个数

4.一减就ac啦

#include<bits/stdc++.h>
using namespace std;
#define N 100011
typedef  long long ll;
typedef pair<ll,int> pii;
int n;
char mp[1011][1011];
bool a[1011][1011];
int dx[8]={-1,-1,0,1,1,1,0,-1};
int dy[8]={0,1,1,1,0,-1,-1,-1};
int wx[4]={-1,0,1,0};
int wy[4]={0,1,0,-1};
bool b[1011][1011];
typedef struct node
{
	int x,y;
}node;
bool check(int x,int y)
{
	if(mp[x][y]=='.') return false;
	if(x+1<=n)
	{
		if(mp[x+1][y]=='.') return false;
	}
	if(y+1<=n) if(mp[x][y+1]=='.') return false;
	if(x-1>=1) if(mp[x-1][y]=='.') return false;
	if(y-1>=1) if(mp[x][y-1]=='.') return false;
	return true;
}
void bfs(int x,int y)///这个bfs是找到了不沉海的岛屿，然后利用bfs染色其岛屿，
					///最后遍历一遍就能知道原来的岛屿中 哪些是不沉的 
{
	a[x][y]=true;
	queue<node> q;
	q.push({x,y});
	while(q.size())
	{
		node t=q.front();
		q.pop();
		int x=t.x,y=t.y;
		for(int i=0;i<4;i++)
		{
			int tx=x+wx[i];
			int ty=y+wy[i];
			if(tx>=1&&tx<=n&&ty>=1&&ty<=n)
			{
				if(!a[tx][ty]&&mp[tx][ty]=='#')
				{
					a[tx][ty]=true;
					q.push({tx,ty});
				}
			}
		}
	}
}
void bfs1(int x,int y)///找总岛屿个数 
{
	b[x][y]=true;
	queue<node> q;
	q.push({x,y});
	while(q.size())
	{
		node t=q.front();
		q.pop();
		int x=t.x,y=t.y;
		for(int i=0;i<4;i++)
		{
			int tx=x+wx[i];
			int ty=y+wy[i];
			if(tx>=1&&tx<=n&&ty>=1&&ty<=n)
			{
				if(!b[tx][ty]&&mp[tx][ty]=='#')
				{
					b[tx][ty]=true;
					q.push({tx,ty});
				}
			}
		}
	}
}
ll an,am;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
    	for(int j=1;j<=n;j++)
    	{
    		cin>>mp[i][j];
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(mp[i][j]=='#'&&!b[i][j])
			{
				bfs1(i,j);
				am++;
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(mp[i][j]=='#'&&check(i,j)&&!a[i][j])///满足check就不沉，一个岛屿有一个就行‘
													///剩下就染色防止重复遍历就行了 
			{
				bfs(i,j);
				an++;
			}
		}
	}
	cout<<am-an;
    return 0;
}