前言
✨本博客讲解 蓝桥杯C/C++ 备赛所涉及算法知识，此博客为第十二讲：图论【习题】
本篇博客所包含习题有：
👊地牢大师
👊全球变暖
👊单链表
👊大臣的旅费
图论【例题】见博客：蓝桥杯第十二讲–图论【例题】
博客内容以题代讲，通过讲解题目的做法来帮助读者快速理解算法内容，需要注意：学习算法不能光过脑，更要实践，请读者务必自己敲写一遍本博客相关代码！！！
地牢大师
题目要求
题目描述：
你现在被困在一个三维地牢中，需要找到最快脱离的出路！
地牢由若干个单位立方体组成，其中部分不含岩石障碍可以直接通过，部分包含岩石障碍无法通过。
向北，向南，向东，向西，向上或向下移动一个单元距离均需要一分钟。
你不能沿对角线移动，迷宫边界都是坚硬的岩石，你不能走出边界范围。
请问，你有可能逃脱吗？
如果可以，需要多长时间？
输入格式：
输出格式：
每组数据输出一个结果，每个结果占一行。
如果能够逃脱地牢，则输出”Escaped in x minute(s).”，其中x xx为逃脱所需最短时间。
如果不能逃脱地牢，则输出”Trapped!”。
数据范围：
1≤L,R,C≤100
输入样例：
3 4 5 S.... .###. .##.. ###.# ##### ##### ##.## ##... ##### ##### #.### ####E 1 3 3 S## #E# ### 0 0 0
输出样例：
Escaped in 11 minute(s). Trapped!
思路分析
也是一道十分典型的 b f s 类问题，和普通的 b f s 只是阶数从 2 维变成了 3 维，具体的操作没有任何变化，唯一不同的就是偏移量的定义要略微因为三维空间发生一些改变，具体代码逻辑同：图论【例题】见博客：蓝桥杯第十二讲–图论【例题】 中的 献给阿尔吉侬的花束
代码
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 110; struct Point { int x, y, z; }; int l, r, c; char g[N][N][N]; int dist[N][N][N]; Point q[N * N * N]; int dx[] = {1, -1, 0, 0, 0, 0}; int dy[] = {0, 0, 1, -1, 0, 0}; int dz[] = {0, 0, 0, 0, 1, -1}; int bfs(int x, int y, int z) { memset(dist, -1, sizeof dist); q[0] = {x, y, z}; dist[x][y][z] = 0; int hh = 0, tt = 0; while (hh <= tt ) { auto t = q[hh ++]; for (int i = 0; i < 6; i ++ ) { int n = t.x + dx[i], m = t.y + dy[i], p = t.z + dz[i]; if (n < 0 || n >= l || m < 0 || m >= r || p < 0 || p >= c) continue; if (dist[n][m][p] != -1) continue; if (g[n][m][p] == '#') continue; dist[n][m][p] = dist[t.x][t.y][t.z] + 1; if (g[n][m][p] == 'E') return dist[n][m][p]; q[ ++ tt] = {n, m, p}; } } return -1; } int main() { while (scanf("%d%d%d", &l, &r, &c), l || r || c) { for (int i = 0; i < l; i ++ ) for (int j = 0; j < r; j ++ ) scanf("%s", g[i][j]); for (int i = 0; i < l; i ++ ) for (int j = 0; j < r; j ++ ) for (int k = 0; k < c; k ++ ) if (g[i][j][k] == 'S') { int distance = bfs(i, j, k); if (distance != -1) printf("Escaped in %d minute(s).\n", distance); else puts("Trapped!"); } } return 0; }
全球变暖
来源： 第九届蓝桥杯省赛C++A/B组,第九届蓝桥杯省赛JAVAA/B组
题目要求
题目描述：
你有一张某海域 N × N 像素的照片，”.”表示海洋、”#”表示陆地，如下所示：
....... .##.... .##.... ....##. ..####. ...###. .......
其中”上下左右”四个方向上连在一起的一片陆地组成一座岛屿，例如上图就有 2 座岛屿。
由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。
具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。
例如上图中的海域未来会变成如下样子：
....... ....... ....... ....... ....#.. ....... .......
请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。
输入格式：
输出格式：
一个整数表示答案。
数据范围：
1≤N≤1000
输入样例1：
7 ....... .##.... .##.... ....##. ..####. ...###. .......
输出样例1：
1
输入样例2：
9 ......... .##.##... .#####... .##.##... ......... .##.#.... .#.###... .#..#.... .........
输出样例2：
1
思路分析
代码
#include <cstdio> #include <cstring> #include <algorithm> #include <queue> #define x first #define y second using namespace std; typedef pair<int, int> PII; const int N = 1010; int n; char g[N][N]; bool st[N][N]; queue<PII> q; int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1}; void bfs(int sx, int sy, int &total, int &bound) { q.push({sx, sy}); st[sx][sy] = true; while (q.size()) { auto t = q.front(); q.pop(); bool is_bound = false; for (int i = 0; i < n; i ++ ) { int x = t.x + dx[i], y = t.y + dy[i]; if (x < 0 || x >= n || y < 0 || y >= n) continue; if (st[x][y]) continue; if (g[x][y] == '.') { is_bound = true; continue; } q.push({x, y}); st[x][y] = true; } total ++; if (is_bound) bound ++; } } int main() { scanf("%d", &n); 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 < n; j ++ ) if (!st[i][j] && g[i][j] == '#') { int total = 0, bound = 0; bfs(i, j, total, bound); if (total == bound) cnt ++; } printf("%d\n", cnt); return 0; }
