643. 动态网格
687. 扫雷
1097. 池塘计数
本题不是上下左右,而是周围八个格,除去中心
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef pair<int, int> PII;
const int N = 1010;
int n, m;
char g[N][N];
bool st[N][N];
PII q[N * N];
void bfs(int x, int y)
{
int hh = 0, tt = 0;
q[0] = {x, y};
st[x][y] = true;
while (hh <= tt)
{
PII t = q[hh ++ ];
for (int i = t.first - 1; i <= t.first + 1; i ++ )
for (int j = t.second - 1; j <= t.second + 1; j ++ )
{
if (i == t.first && j == t.second) continue;
if (i < 0 || i >= n || j < 0 || j >= m) continue;
if (g[i][j] != 'W' || st[i][j]) continue;
st[i][j] = true;
q[++ tt] = {i, j};
}
}
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i ++ ) cin >> 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 ++ ;
}
cout << res << endl;
return 0;
}
1098. 城堡问题
#include <iostream>
#include <algorithm>
#include <cstring>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 55, M = N * N;
int n, m;
PII q[M];
int g[N][N];
bool st[N][N];
int bfs(int sx, int sy)
{
//数组里的x轴正方向是向下的,y轴正方向向右
int dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0};
int hh = 0, tt = 0;
q[0] = {sx, sy};
st[sx][sy] = true;
int area = 0;
while(hh <= tt)
{
PII t = q[hh ++]; //取出队头
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; //如果这个方向是1,说明有墙,不连通
q[ ++ tt] = {a, b};
st[a][b] = true;
}
}
return area;
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 0; i < n; i ++ )
for(int j = 0; j < m; j ++ )
scanf("%d", &g[i][j]);
int cnt = 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));
cnt ++ ;
}
printf("%d\n%d\n", cnt, area);
return 0;
}
作者:NFYD
链接:https://www.acwing.com/activity/content/code/content/1605169/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
1106. 山峰和山谷
#include <iostream>
#include <algorithm>
#include <cstring>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 1010, M = N * N;
int n;
PII q[M];
int g[N][N];
bool st[N][N];
void bfs(int sx, int sy, bool &has_higher, bool &has_lower)
{
int hh = 0, tt = 0;
q[0] = {sx, sy};
st[sx][sy] = true;
while(hh <= tt)
{
PII t = q[hh ++];
//周围八个格都是邻点,按行遍历,特判中心点
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[++ tt] = {i, j};
st[i][j] = true;
}
}
}
}
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\n", peak, valley);
return 0;
}
作者:NFYD
链接:https://www.acwing.com/activity/content/code/content/1605426/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
1113. 红与黑
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef pair<int, int> PII;
const int N = 25, M = N * N;
int n, m;
char g[N][N];
PII q[M];
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int bfs(int x, int y)
{
int hh = 0, tt = 0;
q[0] = {x, y};
g[x][y] = '#';
int res = 0;
while (hh <= tt)
{
PII t = q[hh ++ ];
res ++ ;
for (int i = 0; i < 4; i ++ )
{
int a = t.first + dx[i], b = t.second + dy[i];
if (a < 0 || a >= n || b < 0 || b >= m) continue;
if (g[a][b] != '.') continue;
g[a][b] = '#';
q[++ tt] = {a, b};
}
}
return res;
}
int main()
{
while (cin >> m >> n, n || m)
{
int x = 0, y = 0;
for (int i = 0; i < n; i ++ ) cin >> g[i];
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ )
if (g[i][j] == '@')
{
x = i, y = j;
break;
}
printf("%d\n", bfs(x, y));
}
return 0;
}
1233. 全球变暖
小变形,需要额外统计其他信息
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef pair<int, int> PII;
const int N = 1010;
int n;
bool st[N][N];
char g[N][N];
PII q[N * N];
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
void bfs(int x, int y, int &total, int &bound)
{
int hh = 0, tt = 0;
st[x][y] = true;
q[0] = {x, y};
while (hh <= tt)
{
PII t = q[hh ++ ];
total ++ ;
bool is_bound = false;
for (int i = 0; i < 4; i ++ )
{
int a = t.first + dx[i], b = t.second + dy[i];
if (a < 0 || a >= n || b < 0 || b >= n || st[a][b]) continue;
if (g[a][b] == '.')
{
is_bound = true;
continue;
}
st[a][b] = true;
q[++ tt] = {a, b};
}
if (is_bound) bound ++ ;
}
}
int main()
{
scanf("%d", &n);
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 < n; j ++ )
if (g[i][j] == '#' && !st[i][j])
{
int total = 0, bound = 0;
bfs(i, j, total, bound);
if (total == bound) res ++ ;
}
printf("%d", res);
return 0;
}
1402. 星空之夜
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 110;
int n, m;
PII q[N * N];
char g[N][N];
int top;
double get_dist(PII a, PII b)
{
double dx = a.x - b.x;
double dy = a.y - b.y;
return sqrt(dx * dx + dy * dy);
}
double get_hash()
{
double sum = 0;
for(int i = 0; i < top; i ++ )
for(int j = i + 1; j < top; j ++ )
sum += get_dist(q[i], q[j]);
return sum;
}
char get_id(double key)
{
static double hash[30];
static int id = 0;
for(int i = 0; i < id; i ++ )
if(fabs(hash[i] - key) < 1e-6)
return i + 'a';
hash[id ++ ] = key;
return id - 1 + 'a';
}
void dfs(int a, int b)
{
q[top ++ ] = {a, b};
g[a][b] = '0';
for(int x = a - 1; x <= a + 1; x ++ )
for(int y = b - 1; y <= b + 1; y ++ )
{
if(x == a && y == b) continue;
if(x >= 0 && x < n && y >= 0 && y < m && g[x][y] == '1')
dfs(x, y);
}
}
int main()
{
cin >> m >> n;
for(int i = 0; i < n; i ++ ) cin >> g[i];
for(int i = 0; i < n; i ++ )
for(int j = 0; j < m; j ++ )
if(g[i][j] == '1')
{
top = 0;
dfs(i, j);
char c = get_id(get_hash());
for(int k = 0; k < top; k ++ )
g[q[k].x][q[k].y] = c;
}
for(int i = 0; i < n; i ++ ) cout << g[i] << endl;
return 0;
}
2060. 奶牛选美
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 55, M = N * N;
int n, m;
char g[N][N];
vector<PII> points[2];
int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
PII q[M]; // 这里M为N * N,因为存的是二维下标,见提高课搜索章节池塘计数
bool st[N][N];
void bfs(int x, int y, vector<PII>& ps)
{
int hh = 0, tt = 0;
q[0] = {x, y};
st[x][y] = true;
while(hh <= tt)
{
PII t = q[hh ++];
ps.push_back(t);
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 && g[a][b] == 'X' && !st[a][b])
{
q[++ tt] = {a, b};
st[a][b] = true;
}
}
}
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 0; i < n; i ++ ) cin >> g[i];
for(int i = 0, k = 0; i < n; i ++ )
for(int j = 0; j < m; j ++ )
if(g[i][j] == 'X' && !st[i][j])
bfs(i, j, points[k ++ ]);
int res = 1e8;
for(auto &a : points[0])
for(auto &b : points[1])
res = min(res, abs(a.x - b.x) + abs(a.y - b.y) - 1);
cout << res << endl;
return 0;
}
4004. 传送阵
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 55, M = N * N;
int n;
PII q[M];
char g[N][N];
bool st1[N][N], st2[N][N];
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
void dfs(int x, int y, bool st[][N])
{
st[x][y] = true;
for(int i = 0; i < 4; i ++ )
{
int a = x + dx[i], b = y + dy[i];
if(a >= 0 && a < n && b >= 0 && b < n && !st[a][b] && g[a][b] == '0')
dfs(a, b, st);
}
}
int main()
{
scanf("%d", &n);
int sx, sy, tx, ty;
scanf("%d%d%d%d", &sx, &sy, &tx, &ty);
sx --, sy --, tx --, ty --;
for(int i = 0; i < n; i ++ ) scanf("%s", g[i]);
dfs(sx, sy, st1);
if(st1[tx][ty]) puts("0");
else
{
dfs(tx, ty, st2);
int res = 1e9;
for(int i = 0; i < n; i ++ )
for(int j = 0; j < n; j ++ )
if(st1[i][j])
for(int x = 0; x < n; x ++ )
for(int y = 0; y < n; y ++ )
if(st2[x][y])
res = min(res, (i - x) * (i - x) + (j - y) * (j - y));
printf("%d", res);
}
return 0;
}
标签:PII,专题,int,++,st,Flood,&&,include,Fill
From: https://www.cnblogs.com/Tshaxz/p/16724080.html