Flood Fill求连通块问题

AcWing 1097. 池塘计数

#include<iostream>
#include<queue>
using namespace std;
const int N = 1005;#define x first
#define y second
typedef pair<int,int> PII;
char g[N][N];
queue<PII> q;
int st[N][N];
int n,m;void bfs(int sx,int sy)
{q.push({sx,sy});st[sx][sy] = 1;while(q.size()){PII t = q.front();q.pop();for(int i=t.x-1; i<=t.x+1; i++)for(int j=t.y-1; j<=t.y+1; j++){if(i==t.x && j==t.y) continue; //遍历周围8个格子，将中间格子剔除if(i<0 || i>=n || j<0 || j>=m) continue;if(st[i][j] || g[i][j]=='.') continue;q.push({i,j});st[i][j] = 1;}}
}int main()
{scanf("%d%d",&n,&m);for(int i=0; i<n; i++) scanf("%s",g[i]);int res = 0;for(int i=0; i<n; i++)for(int j=0; j<m; j++)if(g[i][j]=='W' && !st[i][j])//为水且没有标记过{bfs(i,j);res++;} printf("%d",res);return 0;
}

AcWing 1098. 城堡问题

#include<iostream>
#include<queue>
#define x first
#define y secondusing namespace std;const int N = 55;typedef pair<int,int> PII;
int dx[4] = {0,-1,0,1},dy[4] = {-1,0,1,0};int g[N][N];
queue<PII> q;
int st[N][N];
int n,m;int bfs(int sx,int sy)
{q.push({sx,sy});st[sx][sy] = 1;int area = 0;while(q.size()){PII t = q.front();q.pop();area++;for(int i=0; i<4; i++){int a = t.x + dx[i], b = t.y + dy[i];if(a<0 || a>=n || b<0 || b>=m) continue;if(st[a][b]) continue;if(g[t.x][t.y] >> i & 1) continue;//有墙q.push({a,b});st[a][b] = 1;}}return area;
}int main()
{cin >> n >> m;for(int i=0; i<n; i++)for(int j=0; j<m; j++)cin >> g[i][j];int res = 0,area = 0;for(int i=0; i<n; i++)for(int j=0; j<m; j++)if(!st[i][j]){area = max(area,bfs(i,j));res++;}cout << res << endl << area;return 0;
}

AcWing 1106. 山峰和山谷

#include<iostream>
#include<queue>
#define x first
#define y second
using namespace std;typedef pair<int,int> PII;const int N = 1005;
int g[N][N];
queue<PII> q;
int st[N][N];
int n;void bfs(int sx,int sy,bool &has_higher,bool &has_lower)
{q.push({sx,sy});st[sx][sy] = 1;while(q.size()){PII t = q.front();q.pop();for(int i=t.x-1; i<=t.x+1; i++)for(int j=t.y-1; j<=t.y+1; j++){if(i==t.x && j==t.y) continue;if(i<0 || i>=n || j<0 || j>=n) continue;if(g[i][j] != g[t.x][t.y]){if(g[i][j] > g[t.x][t.y]) has_higher = true;else has_lower = true;}else if(!st[i][j]){q.push({i,j});st[i][j] = 1;}}}
}int main()
{scanf("%d",&n);for(int i=0; i<n; i++)for(int j=0; j<n; j++)scanf("%d",&g[i][j]);int peak = 0,valley = 0; //山峰 、山谷for(int i=0; i<n; i++)for(int j=0; j<n; j++)if(!st[i][j]){bool has_higher = false, has_lower = false;bfs(i,j,has_higher,has_lower);if(!has_higher) peak++;if(!has_lower) valley++;}printf("%d %d",peak,valley); 
}