套路：
lood fill搜索
前提条件：求图中连通块数量
我的思路
// // 1≤N≤1000一个整数表示答案。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没依照科学家的预测，照片中有多少岛屿会被完全淹没。
// count
// = ‘。’ is_bound = true;
// if true bound ++;
题解思路：
一个模拟队列（不必要），用一个PII数组模拟PII队列，用两个指针表示队列的front和backfront < back则size为0
push时back++，pop时front++；
函数维护两个值，在bfs外定义这两个值，然后通过引用传入函数中，实现在函数内改变函数外非堆变量的值的效果
题解思路妙在将题目给出的会被淹没的区块和不会被淹没的区块在图中的性质做对比，归结出两种区块的判断条件
#include <algorithm> #include <cstdio> #include <cstring> #include <iostream> using namespace std; #define x first #define y second const int N = 1e3 + 10; char g[N][N]; bool st[N][N]; int n; typedef pair<int,int>PII; PII q[N*N]; int dx[] = {1,-1,0,0},dy[] = {0,0,1,-1}; void bfs(int x ,int y ,int &bound,int &count){ q[0] = {x,y}; st[x][y] = true; int ll = 0,rr = 0; while(ll <= rr){ count ++; x = q[ll].x,y = q[ll].y; ll++; // cout << q[ll].x << " " << q[ll].y << endl; bool is_bound = false; for(int i = 0;i < 4;i++){ int a = x + dx[i]; int b = y + dy[i]; if(st[a][b] ) continue; if(g[a][b] == '.'){ is_bound = true; continue; } if(a < 1 || a > n || b < 1 || b > n ) continue; q[++rr] = {a,b}; st[a][b]= true; } if(is_bound) bound ++; } } int main(){ cin >> n; for(int i = 1;i <= n;i++){ scanf("%s",g[i]); } int cnt = 0; for(int i = 1;i <= n;i++){ for(int j = 1;j <= n;j++){ if(g[i][j] == '#' &&!st[i][j]){ int bound = 0,count = 0; bfs(i,j,bound,count); // cout << bound << " " << count << endl; if(bound ==count) cnt++; } } } cout << cnt << endl; return 0; }
