Flood Fill
AcWing 1097. 池塘计数
题目类型
- BFS
题目链接
思路一
- 遍历每个方块的“八面图”，注意除去中间，即当前方块
- 如果是W且未访问过，则属于同一个池塘
- 直到所有方块没有水为止
AC代码一
// BFS
// BFS
#include <iostream>
#include <cstring>
#include <algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 1010, M = N * N;
int n, m;
char g[N][N];
PII q[M];
bool st[N][N];
void bfs(int sx, int sy)
{
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 >= m ) continue; // 超出边界
if (g[i][j] == '.' || st[i][j]) continue; // 如果此处为空地,跳过
if (g[i][j] == 'W' || !st[i][j])
{
q[++ tt] = {i, j};
st[i][j] = true;
}
}
}
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i ++) scanf("%s", g[i]);
int cnt = 0; // 池塘块
for (int i = 0; i < n; i ++)
{
for (int j = 0; j < m; j ++)
{
// 如果该地有水 且 未访问过 则从此处开始bfs
if (g[i][j] == 'W' && !st[i][j])
{
bfs(i, j);
cnt ++;
}
}
}
cout << cnt << endl;
return 0;
}
思路二
- 用dfs深搜
- 条件与思路一一致，优点在于代码少
AC代码二
// dfs 代码少
#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
char g[N][N];
bool st[N][N];
// 八个方向
int dx[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
int dy[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
void dfs(int sx, int sy)
{
st[sx][sy] = true;
// 八个方向
for (int i = 0; i < 8; i ++ )
{
int nx = sx + dx[i], ny = sy + dy[i];
if (g[nx][ny] == 'W' && !st[nx][ny])
{
dfs(nx, ny);
}
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i ++ ) scanf("%s", g[i]);
int cnt = 0;
for (int i = 0; i < n; i ++ )
{
for (int j = 0; j < m; j ++ )
{
if (g[i][j] == 'W' && !st[i][j])
{
dfs(i, j);
cnt ++;
}
}
}
cout << cnt;
return 0;
}
AcWing 1098. 城堡问题
题目类型
- BFS
- DFS
题目链接
思路一
与上题差不多一致，难点在于输入是可以用二进制表示四周是否有墙，具体看代码
AC代码一
#include <iostream>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 55, M = N * N;
int n, m;
int g[N][N];
PII q[M]; // 队列
bool st[N][N];
int dx[4] = {0, -1, 0, 1} ,dy[4] = {-1, 0, 1, 0}; // 四个方向
int bfs(int sx, int sy)
{
int hh = 0, tt = 0;
int area = 0;
q[0] = {sx, sy};
st[sx][sy] = true;
while (hh <= tt)
{
PII t = q[hh ++];
area ++;
// 遍历四个方向
for (int i = 0; i < 4; i ++ )
{
int nx = t.x + dx[i], ny = t.y + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; // 出界
if (st[nx][ny]) continue; // 访问过
// 用二进制方式,判断是否有墙
if (g[t.x][t.y] >> i & 1) continue;
q[++ tt] = {nx, ny}; // 将当前点入队
st[nx][ny] = true;
}
}
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 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 ++;
}
cout << cnt << endl;
cout << area << endl;
return 0;
}
思路二
与上一题dfs一致
AC代码二
// dfs
#include <iostream>
using namespace std;
const int N = 55;
int g[N][N];
bool st[N][N];
int n, m;
int dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0};
int ans = 0;
int dfs(int sx, int sy)
{
st[sx][sy] = true;
for (int i = 0; i < 4; i ++)
{
int nx = sx + dx[i], ny = sy + dy[i];
if (st[nx][ny]) continue;
if (g[sx][sy] >> i & 1) continue;
ans += dfs(nx, ny);
}
return 1;
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ )
cin >> g[i][j];
int area = 0, cnt = 0;
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ )
if (!st[i][j])
{
cnt ++;
ans = 1;
dfs(i, j);
area = max(area, ans);
}
cout << cnt << endl << area << endl;
return 0;
}
AcWing 1106. 山峰和山谷
题目类型
- BFS
题目链接
思路一
一样还是flood fill类型，不同在于要注意“山脉”，取周围最高的peak和最低的valley，详细看bfs函数代码部分
AC代码一
#include <iostream>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 1010, M = N * N;
int n;
int h[N][N];
PII q[M];
bool st[N][N];
int dx[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
int dy[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int 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 = 0; i < 8; i ++)
{
int nx = t.x + dx[i], ny = t.y + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
if (h[nx][ny] != h[t.x][t.y])
{
if (h[nx][ny] > h[t.x][t.y]) has_higher = true; // 存在山峰
else has_lower = true; // 存在山谷
}
else if (!st[nx][ny])
{
q[++ tt] = {nx, ny};
st[nx][ny] = true;
}
}
}
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ )
for (int j = 0; j < n; j ++ )
scanf("%d", &h[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);
return 0;
}
最短路模型
AcWing 1076. 迷宫问题
题目类型
- BFS
题目链接
思路一
用bfs遍历，为了方便倒着遍历，用pre数组存储上一个访问点
AC代码一
#include <iostream>
#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;
int g[N][N];
PII q[M];
int hh = 0, tt = 0;
PII pre[N][N]; // 存储路径
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
void bfs(int sx, int sy)
{
q[0] = {sx, sy};
pre[sx][sy] = {0, 0};
while (hh <= tt)
{
PII t = q[hh ++];
// 遍历四个方向
for (int i = 0; i < 4; i ++ )
{
int a = t.x + dx[i], b = t.y + dy[i];
if (a < 0 || a > n - 1 || b < 0 || b > n - 1) continue;
if (g[a][b]) continue;
if (pre[a][b].x != -1) continue;
q[++ tt] = {a, b};
pre[a][b] = t;
}
}
}
int main()
{
scanf("%d", &n);
memset(pre, -1, sizeof pre);
for (int i = 0; i < n; i ++ )
for (int j = 0; j < n; j ++ )
scanf("%d", &g[i][j]);
bfs(n - 1, n - 1);
PII end(0, 0);
while (1)
{
printf("%d %d\n", end.x, end.y);
if (end.x == n - 1 && end.y == n - 1) break; // 路径遍历完毕
end = pre[end.x][end.y];
}
return 0;
}
AcWing 188. 武士风度的牛
题目类型
- BFS
题目链接
思路一
用bfs遍历，注意日字型走位的方向向量表示
AC代码一
// 跳“日”字型
#include <iostream>
#include <cstring>
#include <algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 160, M = N * N;
int n ,m; // 行列
char g[N][N];
PII q[M];
int dist[N][N];
int hh = 0, tt = 0;
int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};
int bfs()
{
int sx, sy;
// 寻找起点
for (int i = 0; i < n; i ++ )
for (int j = 0; j < n; j ++ )
if (g[i][j] == 'K') sx = i, sy = j;
q[0] = {sx, sy};
dist[sx][sy] = 0;
while(hh <= tt)
{
PII t = q[hh ++];
for (int i = 0; i < 8; i ++ )
{
int a = t.x + dx[i], b = t.y + dy[i];
if (a < 0 || a >= n || b < 0 || b >= m) continue;//越界
if (g[a][b] == '*') continue; // 障碍物
if (dist[a][b] != -1) continue; // 已经走过
if (g[a][b] == 'H') return dist[t.x][t.y] + 1; // 走到终点
dist[a][b] = dist[t.x][t.y] + 1;
q[++ tt] = {a, b};
}
}
//走不到
return -1;
}
int main()
{
scanf("%d%d", &m, &n);
memset(dist, -1, sizeof dist);
for (int i = 0; i < n; i ++) scanf("%s", g[i]);
printf("%d", bfs());
return 0;
}
AcWing 1100. 抓住那头牛
题目类型
- BFS
题目链接
思路一
三种移动方式
- t + 1
- t - 1
- t * 2
如果能走通，存到dist即可
AC代码一
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
int n, k;
int q[N], hh = 0, tt = 0;;
int dist[N];
int bfs()
{
dist[n] = 0;
q[0] = n;
while (hh <= tt)
{
int t = q[hh ++];
if (t == k) return dist[k]; // 到达目的地
// 三种移动情况
if (t + 1 < N && dist[t + 1] == -1)
{
dist[t + 1] = dist[t] + 1;
q[++ tt] = t + 1;
}
if (t - 1 >= 0 && dist[t - 1] == -1)
{
dist[t - 1] = dist[t] + 1;
q[++ tt] = t - 1;
}
if (t * 2 < N && dist[t * 2] == -1)
{
dist[t * 2] = dist[t] + 1;
q[++ tt] = t * 2;
}
}
return -1;
}
int main()
{
memset(dist, -1, sizeof dist);
scanf("%d%d", &n, &k);
printf("%d", bfs());
return 0;
}
多源BFS
AcWing 173. 矩阵距离
题目类型
- BFS
题目链接
思路一
- 数据范围为1000 一共有1000*1000个格子 用nlogn可能会超时，所以需要想出n的做法
- 这道题多源最短路径问题，可以认为是多起点问题，也就是说，我们可以将所有1为起点的点入队,再利用BFS的层次单调性解决
AC代码一
#include <iostream>
#include <cstring>
#include <algorithm>
#define x first
#define y second
using namespace std;
const int N = 1010, M = N * N;
typedef pair<int, int> PII;
int n, m;
char g[N][N];
PII q[M];
int hh = 0, tt = -1;
int dist[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
void bfs()
{
// 把1都放入队列
for (int i = 0; i < n; i ++ )
{
for (int j = 0; j < m; j ++ )
{
if (g[i][j] == '1')
{
dist[i][j] = 0, q[++ tt] = {i, j};
}
}
}
while (hh <= tt)
{
PII t = q[hh ++];
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 (dist[a][b] != -1) continue; // 访问过
dist[a][b] = dist[t.x][t.y] + 1;
q[++ tt] = {a, b};
}
}
}
int main()
{
memset(dist, -1, sizeof dist); // 初始化
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i ++ )
scanf("%s", g[i]);
bfs();
// 输出结果
for (int i = 0 ; i < n; i ++)
{
for (int j = 0; j < m; j ++) printf("%d ", dist[i][j]);
printf("\n");
}
return 0;
}
最小步数模型
AcWing 1107. 魔板
题目类型
- BFS
题目链接
思路一
AC代码一
##
题目类型
- BFS
题目链接
思路一
AC代码一
