全球变暖-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;
}