对于染色问题，可以采用BFS求解
BFS的优点是：每个点只会遍历一次，第一次遇到终点时即可求得最短路
1097. 池塘计数
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
char a[1010][1010];
bool st[1010][1010];
int bx[8] = {1,-1,0,0,1,1,-1,-1};
int by[8] = {0,0,1,-1,1,-1,1,-1};
int ans = 0;
int n,m;
void bfs(int x, int y)
{
if(a[x][y] == '.')return;
queue<pair<int,int>> q;
q.push({x,y});
while(!q.empty())
{
int nowx = q.front().first;
int nowy = q.front().second;
q.pop();
for(int i = 0; i < 8; i ++ )
{
int nx = nowx + bx[i];
int ny = nowy + by[i];
if(nx < 1 || ny < 1 || nx > n || ny > m)continue;
if(a[nx][ny] == '.')continue;
if(st[nx][ny])continue;
q.push({nx, ny});
st[nx][ny] = true;
}
}
ans ++;
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++ )
{
for(int j = 1; j <= m; j ++ )
{
cin >> a[i][j];
}
}
for(int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
{
if(!st[i][j])
bfs(i,j);
}
cout << ans;
}
1098. 城堡问题
// 2
// 1 4
// 8
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#define fi first
#define se second
#define PII pair<int,int>
using namespace std;
int n, m;
int cnt = 0, area = 0;
int a[100][100];
bool st[100][100];
int bx[4] = {0,-1,0,1};
int by[4] = {-1,0,1,0};
void bfs(int x, int y)
{
int num = 0;
queue<PII>q;
q.push({x,y});
num ++;
st[x][y] = true;
while(!q.empty())
{
auto t = q.front();
q.pop();
int nowx = t.fi, nowy = t.se;
for(int i = 0; i < 4; i ++ )
if(!((a[nowx][nowy] >> i)&1 ))
{
int nx = nowx + bx[i], ny = nowy + by[i];
if(nx < 1 || ny < 1 || nx > n || ny > m)continue;
if(st[nx][ny])continue;
q.push({nx,ny});
num ++;
st[nx][ny] = true;
}
}
cnt ++;
area = max(area, num);
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++ )
for(int j = 1; j <= m; j ++ )
cin >> a[i][j];
for(int i = 1; i <= n; i ++ )
for(int j = 1; j <= m; j ++)
{
if(!st[i][j])
bfs(i, j);
}
cout << cnt << endl << area;
}
1106. 山峰和山谷
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#define fi first
#define se second
#define PII pair<int,int>
using namespace std;
int n;
int bx[8] = {1,1,1,-1,-1,-1,0,0};
int by[8] = {0,1,-1,0,1,-1,1,-1};
int a[1010][1010];
bool st[1010][1010];
int cnt1 = 0, cnt2 = 0;
void bfs(int x, int y)
{
bool flag[2] = {0, 0};
queue<PII> q;
q.push({x,y});
st[x][y] = true;
while(!q.empty())
{
auto t = q.front();
int nowx = t.fi, nowy = t.se;
q.pop();
for(int i = 0; i < 8; i ++ )
{
int nx = nowx + bx[i], ny = nowy + by[i];
if(nx < 1 || ny < 1 || nx > n || ny > n)continue;
if(a[nowx][nowy] < a[nx][ny])
flag[0] = true;
else if(a[nowx][nowy] > a[nx][ny])
flag[1] = true;
else if(!st[nx][ny])
{
q.push({nx, ny});
st[nx][ny] = true;
}
}
}
if(flag[0]&&!flag[1])cnt1++;
if(!flag[0]&&flag[1])cnt2++;
if(!flag[0]&&!flag[1]){
cnt1 = 1;
cnt2 = 1;
}
}
int main()
{
cin >> n;
for(int i = 1; i <= n; i ++ )
for(int j = 1; j <= n; j ++ )
{
cin >> a[i][j];
}
for(int i = 1; i <= n; i ++ )
for(int j = 1; j <= n; j ++ )
{
if(!st[i][j])
bfs(i,j);
}
cout << cnt2 << " " << cnt1;
}
