搜索题（BFS、DFS）

1.[蓝桥杯 2018 省 AB] 全球变暖

P8662 [蓝桥杯 2018 省 AB] 全球变暖 – 洛谷

1.题目描述

你有一张某海域 N×N 像素的照片，. 表示海洋、 # 表示陆地，如下所示：

…….
.##….
.##….
….##.
..####.
…###.
…….

其中 "上下左右" 四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有 2 座岛屿。

由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻（上下左右四个相邻像素中有海洋），它就会被淹没。

例如上图中的海域未来会变成如下样子：

…….
…….
…….
…….
….#..
…….
…….

请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。

输入格式

第一行包含一个整数 N。(1≤N≤1000)。

以下 N 行 N 列代表一张海域照片。

照片保证第 1 行、第 1 列、第 N 行、第 N 列的像素都是海洋。

输出格式

一个整数表示答案。

输入输出样例

输入 #1复制

7
…….
.##….
.##….
….##.
..####.
…###.
…….

输出 #1复制

1

说明/提示

时限 1 秒, 256M。蓝桥杯 2018 年第九届省赛

2.分析

简单的暴力题，BFS遍历图一遍即可。

如果有一块陆地上下左右都是陆地，那么这块陆地就不会被淹没。

另外有一个细节，就是当遍历到其中一个点是陆地 '#’ 时，要用其他符号标记这个点，即把这个点由 '#' 改为 '.'   '*'  等，可以是与图中的海洋的标记相同，也可以避免与图中两点重复。

3.编程思路

功能解析

计算一个由字符矩阵表示的地图中，有多少岛屿会被完全淹没。岛屿由 # 表示，海洋由 . 表示。岛屿被定义为相邻的 # 组成的连通块，如果一个岛屿的所有 # 都不与海洋相邻（即四周都是 # 或其他岛屿），则该岛屿不会被淹没。

输入处理 从标准输入读取一个 n x n 的字符矩阵，矩阵中的 # 表示陆地，. 表示海洋。

岛屿遍历 使用深度优先搜索（DFS）遍历每个岛屿。对于每个岛屿，检查其所有陆地像素是否至少有一个方向与海洋相邻。如果存在至少一个陆地像素四周无海洋（即四周都是 # 或其他岛屿），则该岛屿不会被淹没。

淹没判断

• 变量 t 用于标记当前岛屿是否至少有一个不会被淹没的陆地像素。
• 变量 sum 记录总岛屿数量。
• 变量 ans 记录不会被淹没的岛屿数量。

输出结果 最终输出被淹没的岛屿数量，即 sum – ans。

4.代码实现（C++）

#include<bits/stdc++.h>
using namespace std;

// 全局变量声明
int n; // 地图尺寸
int cnt; // 计数器，用于统计某个陆地像素周围海洋的数量
int sum; // 岛屿总数量
int ans; // 不会被淹没的岛屿数量
int f; // 标记当前岛屿是否已经确定不会被淹没（0-未确定/会被淹，1-不会被淹）

// 方向数组：右、下、左、上
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

char mp[1010][1010]; // 存储地图

// 深度优先搜索函数，用于遍历一个岛屿的所有像素
// x, y: 当前搜索的像素坐标
void dfs(int x, int y) {
// 如果当前岛屿的淹没状态还未确定（f==0），检查当前像素是否四周都不是海洋
if (!f) {
cnt = 0;
// 遍历四个方向
for (int i = 0; i < 4; i++) {
// 如果相邻像素不是海洋（即不是'.'），计数器加1
if (mp[x + dx[i]][y + dy[i]] != '.') {
cnt++;
}
}
// 如果四个方向都不是海洋，说明这个岛屿至少有一个像素是“内陆”，不会被完全淹没
if (cnt == 4) {
ans++; // 不会被淹没的岛屿数量加1
f = 1; // 标记该岛屿为不会被淹没
}
}

// 将当前像素标记为已访问（用'*'表示）
mp[x][y] = '*';

// 继续搜索四个方向相邻的像素
for (int i = 0; i < 4; i++) {
int xx = x + dx[i];
int yy = y + dy[i];

// 边界检查：如果越界或者相邻像素不是未访问的陆地（'#'），则跳过
if (xx < 0 || xx >= n || yy < 0 || yy >= n || mp[xx][yy] != '#') {
continue;
}
dfs(xx, yy); // 递归搜索相邻陆地
}
}

int main() {
cin >> n; // 读入地图尺寸

// 读入地图数据
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> mp[i][j];
}
}

// 遍历地图（避开边界，因为题目保证第 1 行、第 1 列、第 N 行、第 N 列的像素都是海洋。）
for (int i = 1; i < n – 1; i++) {
for (int j = 1; j < n – 1; j++) {
// 如果发现未访问的陆地（'#'），说明找到了一个新的岛屿
if (mp[i][j] == '#') {
sum++; // 岛屿总数加1
f = 0; // 初始化该岛屿的淹没状态为“未确定”
dfs(i, j); // 深度优先搜索整个岛屿
}
}
}

// 输出结果：总岛屿数 – 不会被淹没的岛屿数 = 会被淹没的岛屿数
cout << sum – ans;

return 0;
}

5.关键点总结

• 淹没条件：岛屿中至少有一个陆地像素四周无海洋。
• DFS作用：标记连通块并检查淹没条件。
• 性能：时间复杂度为 O(n^2)，适用于 n <= 1000 的规模。

6.广度优先遍历（BFS）做法

此处附上代码和简单的说明

#include <iostream>
#include <queue>
using namespace std;

// N: 地图的最大尺寸（常量）
const int N = 1005;

// a[N][N]: 二维字符数组，存储地图信息，'#'表示陆地，'.'表示海洋，'*'表示已访问的陆地
char a[N][N];
// n: 地图的实际边长
int n;

// 方向数组：上、左、右、下
int dx[] = {-1, 0, 0, 1};
int dy[] = {0, -1, 1, 0};

// BFS函数，参数 (x,y) 是岛屿的起点坐标
// 返回值：该岛屿中不会被海水淹没的陆地数量
int bfs(int x, int y) {
// 手动实现队列的数组：qx 存储横坐标，qy 存储纵坐标
int qx[N * N], qy[N * N];
// front: 队列头部索引（即将出队的位置）
// rear: 队列尾部索引（下一个入队的位置）
int front = 0, rear = 0;

// 将起始点加入队列
qx[rear] = x;
qy[rear] = y;
rear++;

// 标记起始点为已访问（避免重复访问）
a[x][y] = '*';

// left: 计数器，记录该岛屿中不会被淹没的陆地数量
int left = 0;

// BFS 主循环：当队列不为空时继续处理
while (front < rear) {
// 取出队首元素（当前处理的陆地坐标）
int curx = qx[front];
int cury = qy[front];
front++;

// landCount: 统计当前陆地四周（上下左右）的陆地数量
int landCount = 0;

// 检查四个方向
for (int i = 0; i < 4; i++) {
// 计算相邻位置的坐标
int nx = curx + dx[i];
int ny = cury + dy[i];

// 检查边界：如果越界则跳过
if (nx < 0 || nx >= n || ny < 0 || ny >= n)
continue;

// 如果相邻位置是未访问的陆地
if (a[nx][ny] == '#') {
landCount++; // 陆地计数加1
qx[rear] = nx; // 加入队列
qy[rear] = ny;
rear++;
a[nx][ny] = '*'; // 标记为已访问
} else if (a[nx][ny] == '*') { // 如果相邻位置是已访问的陆地
landCount++; // 陆地计数加1（但不再重复入队）
}
// 注意：相邻位置是海洋（'.'）时，landCount 不增加
}

// 如果当前陆地四周都是陆地（landCount == 4），则它不会被海水淹没
if (landCount == 4) {
left++; // 不会被淹没的陆地数量加1
}
}

// 返回该岛屿中不会被淹没的陆地数量
return left;
}

int main() {
// 读入地图边长
cin >> n;

// 读入地图数据
for (int i = 0; i < n; i++) {
cin >> a[i];
}

// ans: 最终结果，统计会被完全淹没的岛屿数量（整个岛屿中没有一块不会被淹没的陆地）
int ans = 0;

// 遍历整个地图
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// 如果找到未访问的陆地（即一个新岛屿的起点）
if (a[i][j] == '#') {
// 对该岛屿进行BFS遍历，如果返回值为0，表示整个岛屿都会被淹没
if (bfs(i, j) == 0) {
ans++; // 被淹没的岛屿数量加1
}
// 注意：如果 bfs 返回值 > 0，说明该岛屿至少有一块陆地不会被淹没，不计入 ans
}
}
}

// 输出结果
cout << ans << endl;

return 0;
}

关键逻辑说明：

示例：

输入： 4 #… ##.. ..#. ###.

输出： 1

• 左上角的岛屿（坐标(0,0)和(1,0)、(1,1)）中，只有(1,1)的四周都是陆地（上下左右都是'#'），因此该岛屿不会被完全淹没。

• 右下角的岛屿（(2,2)、(3,2)、(3,3)）中，没有一块陆地四周都是陆地（至少有一面是海洋），因此该岛屿会被完全淹没。

• 最终 ans = 1。

2.[蓝桥杯 2018 国 C] 迷宫与陷阱

P8673 [蓝桥杯 2018 国 C] 迷宫与陷阱 – 洛谷

1.题目描述

小明在玩一款迷宫游戏，在游戏中他要控制自己的角色离开一间由 N×N 个格子组成的二维迷宫。

小明的起始位置在左上角，他需要到达右下角的格子才能离开迷宫。

每一步，他可以移动到上下左右相邻的格子中（前提是目标格子可以经过）。

迷宫中有些格子小明可以经过，我们用 . 表示；

有些格子是墙壁，小明不能经过，我们用 # 表示。

此外，有些格子上有陷阱，我们用 X 表示。除非小明处于无敌状态，否则不能经过。

有些格子上有无敌道具，我们用 % 表示。

当小明第一次到达该格子时，自动获得无敌状态，无敌状态会持续 K 步。

之后如果再次到达该格子不会获得无敌状态了。

处于无敌状态时，可以经过有陷阱的格子，但是不会拆除 / 毁坏陷阱，即陷阱仍会阻止没有无敌状态的角色经过。

给定迷宫，请你计算小明最少经过几步可以离开迷宫。

输入格式

第一行包含两个整数 N 和 K。(1≤N≤1000，1≤K≤10)。

以下 N 行包含一个 N×N 的矩阵。

矩阵保证左上角和右下角是 .。

输出格式

一个整数表示答案。如果小明不能离开迷宫，输出 −1。

输入输出样例

输入 #1复制

5 3
…XX
##%#.
…#.
.###.
…..

输出 #1复制

10

输入 #2复制

5 1
…XX
##%#.
…#.
.###.
…..

输出 #2复制

12

说明/提示

时限 3 秒, 256M。蓝桥杯 2018 年第九届国赛

2.思路

我们可以将这道题理解为带状态的 BFS（广度优先搜索）。 状态不仅包括位置 (x, y)，还包括当前剩余的无敌步数 inv。

普通的迷宫 BFS 中，每个格子的访问状态是 visited[x][y]。 但是这里因为有无敌状态持续 K 步，所以同一个格子在不同剩余无敌步数时访问的情况是不同的。

比如：

• 第一次到达 (x, y) 时 inv= 0，路径长度是 step1

• 第二次到达 (x, y) 时 inv= 3，路径长度是 step2

即便 step2 > step1，也有可能因为 inv更大而能在后续走更多陷阱格子，所以两种状态都要考虑。

因此状态空间为：

状态 = (x, y, inv)

其中 0 ≤ inv≤ K。

3.访问记录优化

我们可以用一个数组 best_inv[x][y] 表示：到达 (x, y) 时，曾经达到过的最大剩余无敌步数。 为什么这样可行？ 因为对于同一个位置 (x, y)：

• 如果现在到达时 inv比以前到达时的最大剩余无敌步数还要小或相等，那么这次访问是不必要的（之前访问时既可以走更多步无敌，步数还可能更少）。

• 反之，如果现在到达时 inv比以前记录的最大剩余无敌步数更大，那么这次访问可能带来更好的后续路径（能穿越更多陷阱），需要入队。

因此剪枝条件为：

如果当前 inv<= best_inv[x][y]，则跳过。
否则更新 best_inv[x][y] = inv，并继续。

4.状态转移

从 (x, y, inv) 向四个方向扩展：

实际上更准确的描述是：

• 如果当前剩余无敌步数为 m，走一步到下一个格子时：

  • 如果下一个格子是 %，则先获得 K 步无敌（覆盖原有的剩余步数），因此新魔法值 = K。

  • 否则，新魔法值 = max(m – 1, 0)。

5.算法步骤

6.代码实现（C++）

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

// 状态结构体：表示BFS搜索过程中的一个状态
struct State {
int x, y; // 当前位置坐标
int inv; // 剩余无敌步数 (invincible的缩写)
int step; // 从起点到当前位置的步数
};

int N, K; // N: 迷宫大小，K: 无敌道具持续步数
char grid[1005][1005]; // 迷宫地图
int best_inv[1005][1005]; // 记录到达每个位置时的最大剩余无敌步数（用于剪枝）

// 四个方向的移动向量：右、下、左、上
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

// BFS搜索函数
int bfs() {
// 初始化best_inv数组为-1，表示所有位置都未被访问过
memset(best_inv, -1, sizeof(best_inv));

// BFS队列
queue<State> q;

// 起点状态：(0,0)位置，无敌步数为0，已走0步
q.push({0, 0, 0, 0});
best_inv[0][0] = 0; // 起点处的最大无敌步数为0

while (!q.empty()) {
// 取出队首状态
State cur = q.front();
q.pop();

// 如果到达终点，返回步数（终点保证是'.'，不需要无敌状态）
if (cur.x == N – 1 && cur.y == N – 1) {
return cur.step;
}

// 尝试四个方向的移动
for (int i = 0; i < 4; i++) {
int nx = cur.x + dx[i]; // 新位置的x坐标
int ny = cur.y + dy[i]; // 新位置的y坐标

// 边界检查：新位置是否在迷宫范围内
if (nx < 0 || nx >= N || ny < 0 || ny >= N)
continue;

// 初始化新状态的无敌步数为当前无敌步数
int new_inv = cur.inv;

// 根据新位置的格子类型进行不同的处理
if (grid[nx][ny] == '#') {
// 墙壁：不能通过
continue;
}
else if (grid[nx][ny] == 'X') {
// 陷阱：只有当有无敌状态时才能通过
if (cur.inv == 0)
continue; // 没有无敌状态，不能通过陷阱
new_inv = cur.inv – 1; // 通过陷阱后无敌步数减1
}
else if (grid[nx][ny] == '%') {
// 无敌道具：获得K步无敌（覆盖原有无敌步数）
new_inv = K; // 注意：是直接设置为K，不是cur.inv + K
}
else { // '.' 普通路径
// 无论是否有无敌状态，移动一步后无敌步数都会减少（最小为0）
new_inv = max(cur.inv – 1, 0);
}

// ========== 关键剪枝操作 ==========
// 如果新状态的无敌步数没有超过之前到达该位置时的最大无敌步数，
// 那么这个状态就不需要继续探索（因为之前有更好的状态）
if (new_inv > best_inv[nx][ny]) {
// 更新该位置的最大无敌步数记录
best_inv[nx][ny] = new_inv;
// 将新状态加入队列继续搜索
q.push({nx, ny, new_inv, cur.step + 1});
}
}
}

// 队列为空仍未到达终点，说明无法到达
return -1;
}

int main() {
// 读入迷宫大小和无敌持续时间
cin >> N >> K;

// 读入迷宫地图
for (int i = 0; i < N; i++) {
cin >> grid[i]; // 按行读入字符串
}

// 调用BFS函数并输出结果
cout << bfs() << endl;

return 0;
}

7. 时间复杂度

• 每个位置最多被访问 K+1 次

• 复杂度：O(N² × K) ≈ 10⁷ 级别，可接受

8. 易错点

• 道具格子只生效一次，但剪枝自动处理

• 无敌步数减少发生在移动后，不是在原地减少

• 到达终点不需要无敌状态，终点保证是 .

一句话总结：用 (x,y,inv) 作为状态进行 BFS，通过 best_inv 剪枝避免重复搜索。

3.[蓝桥杯 2023 国 B] AB 路线

P9425 [蓝桥杯 2023 国 B] AB 路线 – 洛谷

1.题目描述

有一个由 N×M 个方格组成的迷宫，每个方格写有一个字母 A 或者 B。小蓝站在迷宫左上角的方格，目标是走到右下角的方格。他每一步可以移动到上下左右相邻的方格去。

由于特殊的原因，小蓝的路线必须先走 K 个 A 格子、再走 K 个 B 格子、再走 K 个 A 格子、再走 K 个 B 格子……如此反复交替。

请你计算小蓝最少需要走多少步，才能到达右下角方格？

注意路线经过的格子数不必一定是 K 的倍数，即最后一段 A 或 B 的格子可以不满 K 个。起点保证是 A 格子。

例如 K=3 时，以下 3 种路线是合法的：

AA
AAAB
AAABBBAAABBB

以下 3 种路线不合法：

ABABAB
ABBBAAABBB
AAABBBBBBAAA

输入格式

第一行包含三个整数 N、M 和 K。

以下 N 行，每行包含 M 个字符（A 或 B），代表格子类型。

输出格式

一个整数，代表最少步数。如果无法到达右下角，输出 −1。

输入输出样例

输入 #1复制

4 4 2
AAAB
ABAB
BBAB
BAAA

输出 #1复制

8

说明/提示

样例说明

每一步方向如下：下右下右上右下下；路线序列： AABBAABBA。

评测用例规模与约定

• 对于 20% 的数据，1≤N,M≤4。
• 对于另 20% 的数据，K=1。
• 对于 100% 的数据，1≤N,M≤1000，1≤K≤10。

第十四届蓝桥杯大赛软件赛决赛 C/C++ 大学 B 组 G 题

2. 题目要求解读

核心理解：这是一个 带状态约束的BFS 问题，状态 = (位置x, 位置y, 连续相同字母已走步数s)

• 路线必须交替走A和B，且每组连续相同字母最多走K步

• 路线序列示例：AABBAABBA (K=3时合法)

• 关键约束：不能连续走超过K个相同字母

• 如果当前已连续走s个A，下一个格子必须是：

  • 如果s < K：只能走A

  • 如果s = K：必须走B，且重置计数器

2. 状态定义

struct node {
int x, y; // 当前位置
int step; // 已走总步数
int s; // 当前字母已连续走了几步 (1 ≤ s ≤ K)
}

3. 状态转移规则

情况1：当前字母没走够K步 (s < K)

只能走相同字母的格子
新状态：s = s + 1

情况2：当前字母已走够K步 (s = K)

必须换字母
新状态：s = 1 (重新开始计数)

4. 访问标记

由于状态中多了s这个维度，所以需要三维访问标记：

bool vis[N][N][15]; // vis[x][y][s] 表示是否以连续走了s步的状态访问过(x,y)

同一位置，以不同的s值到达，代表不同的状态，都需要探索。

5.代码实现（C++）

#include<bits/stdc++.h>
using namespace std;

const int N = 1e3 + 5;

// 方向数组：左、上、右、下（注意与常规顺序可能不同）
const int dx[4] = {0, -1, 0, 1};
const int dy[4] = {-1, 0, 1, 0};

int n, m, k; // n行，m列，每组最多连续k个
char c[N][N]; // 存储迷宫字母

// 三维访问标记：vis[x][y][s]
// 表示是否以"连续走了s个相同字母"的状态访问过(x,y)位置
bool vis[N][N][15];

// 状态结构体
struct node {
int x, y; // 当前位置坐标
int step; // 从起点到当前位置的总步数
int s; // 当前字母已连续走了几步 (1 ≤ s ≤ k)
};

void bfs() {
queue<node> q;
// 起点状态：在(1,1)，走了0步，当前字母A已连续走了1步
q.push({1, 1, 0, 1});

while(!q.empty()) {
// 取出队首状态
int x = q.front().x;
int y = q.front().y;
int step = q.front().step;
int s = q.front().s;
q.pop();

// 如果到达终点，输出答案
// 注意：题目允许最后一段不满k个，所以任意s值都可以到达终点
if(x == n && y == m) {
cout << step;
return;
}

// 如果这个状态已经访问过，跳过（BFS第一次到达就是最短路径）
if(vis[x][y][s]) continue;
vis[x][y][s] = true; // 标记访问

if(s == k) { // 情况1：当前字母已经走够了k个，必须换字母
char current_char = c[x][y];
for(int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
// 边界检查 + 字母必须不同
if(nx >= 1 && nx <= n && ny >= 1 && ny <= m
&& c[x][y] != c[nx][ny]) {
// 换字母后，新字母的连续计数从1开始
q.push({nx, ny, step+1, 1});
}
}
} else { // 情况2：当前字母还没走够k个，必须继续走相同字母
for(int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
// 边界检查 + 字母必须相同
if(nx >= 1 && nx <= n && ny >= 1 && ny <= m
&& c[x][y] == c[nx][ny]) {
// 相同字母，连续计数加1
q.push({nx, ny, step+1, s+1});
}
}
}
}

// BFS结束还没找到终点，说明无法到达
cout << -1;
}

int main() {
cin >> n >> m >> k;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
cin >> c[i][j];
bfs();
return 0;
}

6.时间复杂度分析

• 状态数：O(n × m × k) ≈ 1000×1000×10 = 10⁷

• 每个状态扩展4个方向

• 总复杂度：O(4 × n × m × k) ≈ 4×10⁷，在1秒内可接受

7.易错点和注意事项

8.总结

这道题的关键在于将 连续相同字母的计数 作为状态的一部分，从而将问题转化为三维状态空间的BFS搜索。这种方法在蓝桥杯等竞赛中常见，是 带约束的BFS 的典型应用。