# [Floodfill model in search]

1.ACW1097: Pond count
Title:'W': Water,'.': Dry, find the number of puddles.
Idea: The most basic Floodfill.
The code is as follows:

```#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N = 1010;
typedef long long LL;
typedef pair<LL, LL> PII;
char c[N][N];
LL n,m;
bool st[N][N];
int dx = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy = {-1, 0, 1, 1, 1, 0, -1, -1};
void bfs(LL sta,LL ed)
{
queue<PII>q;q.push({sta,ed});st[sta][ed]=true;
while(q.size())
{
PII t=q.front();q.pop();
for(int i=0;i<8;i++)
{
LL ix=t.x+dx[i],iy=t.y+dy[i];
if(ix<=0||iy<=0||ix>n||iy>m||st[ix][iy]||c[ix][iy]=='.') continue;
q.push({ix,iy});st[ix][iy]=true;
}
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) cin>>c[i][j];
LL ans=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(!st[i][j]&&c[i][j]=='W')
{
bfs(i,j);
ans++;
}
cout<<ans;
return 0;
}
```

2.ACW1098: The Castle Problem
Inscription: Each grid has a number indicating which direction of the four directions there is a wall. Two cells without a wall are connected to a room to find the maximum number of rooms. Among them, 1: West Wall, 2: North Wall, 3: East Wall, 4: South Wall, [can be added up, for example, if there are four walls, this grid is 15.)
Idea: It is unnecessary to build a graph and find out if every bit of a grid is 1 by binary judgment. A 1 means that the grid has a wall in its current corresponding orientation, so it is not connected to the next-wall grid structure in this direction and will not be added to the queue naturally.
The code is as follows:

```#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#define x first
#define y second
using namespace std;
const int N = 55;
typedef long long LL;
typedef pair<int, int> PII;
LL c[N][N],n,m,t,res;
bool st[N][N];
int dx={0,-1,0,1},dy={-1,0,1,0};
void bfs(LL sta,LL ed)
{
queue<PII>q;q.push({sta,ed});st[sta][ed]=true;LL area=0;
while(q.size())
{
PII t=q.front();q.pop();area++;
for(int i=0;i<4;i++)
{
LL ix=t.x+dx[i],iy=t.y+dy[i];
if(ix<1||iy<1||ix>n||iy>m||st[ix][iy]) continue;
if(!(c[t.x][t.y]>>i&1)) {q.push({ix,iy});st[ix][iy]=true;}
}
}
res=max(area,res);
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) cin>>c[i][j];
LL ans=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(!st[i][j]) {bfs(i,j);ans++;}
cout<<ans<<endl;
cout<<res;
return 0;
}
```

3.ACW1106: Peaks and Valleys
Topic:
We define a grid whose set S is a mountain (valley) if and only if:
(1) All the lattices of S have the same height.
(2) All the lattices of S are connected.
(3) For s belongs to S, the s'adjacent to s does not belong to S, and there are ws>ws' (mountain peak) or ws<ws'(valley).
(4) If there is no adjacent area around it, consider it both a mountain and a valley.
Idea: Floodfill finds each connected block and marks the points it is adjacent to as large and as small as possible:
If there are any larger or smaller lattices, the connection block is neither a mountain nor a valley.
(2) If there is only one larger than it, it cannot be smaller: the connecting block is a valley.
(3) If only smaller than it is, it cannot be larger: the connecting block is a mountain peak.
(4) If it is neither so large nor so small, it is equal to all the lattices in the current connected block: those lattices that are equal to the connected block are also part of the connected block.
The code is as follows:

```#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int N = 1010;
typedef long long LL;
typedef pair<int, int> PII;
LL c[N][N],n,m,t,low,peak;
bool st[N][N];
int dx = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy = {-1, 0, 1, 1, 1, 0, -1, -1};
void bfs(LL x,LL y,bool &has_high,bool &has_low)
{
queue<PII>q;q.push({x,y});st[x][y]=true;
while(q.size())
{
PII t=q.front();q.pop();
for(int i=0;i<8;i++)
{
LL ix=t.x+dx[i],iy=t.y+dy[i];
if(ix<1||iy<1||ix>n||iy>n) continue;
if(c[ix][iy]>c[t.x][t.y]) has_low=true;
else if(c[ix][iy]<c[t.x][t.y]) has_high=true;
else if(c[ix][iy]==c[t.x][t.y])
{
if(!st[ix][iy]) {q.push({ix,iy});st[ix][iy]=true;}
}
}
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) cin>>c[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(!st[i][j])
{
bool has_high=false,has_low=false;
bfs(i,j,has_high,has_low);
if(!has_low) peak++;
if(!has_high) low++;
}
cout<<peak<<' '<<low;
return 0;
}
```

Keywords: C++ Algorithm

Added by erth on Sun, 13 Feb 2022 20:19:22 +0200