前言
✨本博客讲解 蓝桥杯C/C++ 备赛所涉及算法知识，此博客为第十二讲：图论【例题】
本篇博客所包含习题有：
👊献给阿尔吉侬的花束
👊红与黑
👊交换瓶子
图论【习题】见博客：蓝桥杯第十二讲–图论【习题】
BFS、D F S 算法模板见博客：树与图的遍历：DFS，BFS 算法模板
BFS知识讲解见博客：BFS
博客内容以题代讲，通过讲解题目的做法来帮助读者快速理解算法内容，需要注意：学习算法不能光过脑，更要实践，请读者务必自己敲写一遍本博客相关代码！！！
献给阿尔吉侬的花束
题目要求
题目描述：
阿尔吉侬是一只聪明又慵懒的小白鼠，它最擅长的就是走各种各样的迷宫。
今天它要挑战一个非常大的迷宫，研究员们为了鼓励阿尔吉侬尽快到达终点，就在终点放了一块阿尔吉侬最喜欢的奶酪。
现在研究员们想知道，如果阿尔吉侬足够聪明，它最少需要多少时间就能吃到奶酪。
迷宫用一个 R × C 的字符矩阵来表示。
字符 S 表示阿尔吉侬所在的位置，字符 E 表示奶酪所在的位置，字符 # 表示墙壁，字符 . 表示可以通行。
阿尔吉侬在 1 个单位时间内可以从当前的位置走到它上下左右四个方向上的任意一个位置，但不能走出地图边界。
输入格式：
第一行是一个正整数 T，表示一共有 T 组数据。
每一组数据的第一行包含了两个用空格分开的正整数 R 和 C ，表示地图是一个 R × C 的矩阵。
接下来的 R 行描述了地图的具体内容，每一行包含了 C 个字符。字符含义如题目描述中所述。保证有且仅有一个 S 和 E 。
输出格式：
对于每一组数据，输出阿尔吉侬吃到奶酪的最少单位时间。
若阿尔吉侬无法吃到奶酪，则输出“oop!”（只输出引号里面的内容，不输出引号）。
每组数据的输出结果占一行。
数据范围：
1<T≤10,
2≤R,C≤200
输入样例：
3 3 4 .S.. \#\#\#\. ..E. 3 4 .S.. .E.. .... 3 4 .S.. \#\#\#\# ..E.
输出样例：
5 1 oop!
思路分析
代码
#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 = 210; int n, m; char g[N][N]; int dist[N][N]; int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; int bfs(int x, int y) { queue<PII> q; memset(dist, -1, sizeof dist); dist[x][y] = 0; q.push({x, y}); while (q.size()) { auto t = q.front(); q.pop(); for (int i = 0; i < 4; i ++ ) { int x = t.x + dx[i], y = t.y + dy[i]; if (x < 0 || x >= n || y < 0 || y >= m) continue; if (g[x][y] == '#') continue; if (dist[x][y] != -1) continue; dist[x][y] = dist[t.x][t.y] + 1; if (g[x][y] == 'E') return dist[x][y]; q.push({x, y}); } } return -1; } int main() { int T; scanf("%d", &T); while (T -- ) { scanf("%d%d", &n, &m); for (int i = 0; i < n; i ++ ) scanf("%s", g[i]); for (int i = 0; i < n; i ++ ) for (int j = 0; j < m; j ++ ) if (g[i][j] == 'S') { int res = bfs(i, j); if (res != -1) printf("%d\n", res); else puts("oop!"); break; } } return 0; }
红与黑
题目要求
题目描述：
有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。
你站在其中一块黑色的瓷砖上，只能向相邻（上下左右四个方向）的黑色瓷砖移动。
请写一个程序，计算你总共能够到达多少块黑色的瓷砖。
输入格式：
输入包括多个数据集合。
每个数据集合的第一行是两个整数 W 和 H ，分别表示 x 方向和 y 方向瓷砖的数量。
在接下来的 H行中，每行包括 W 个字符。每个字符表示一块瓷砖的颜色，规则如下：
1）‘.’：黑色的瓷砖；
2）‘#’：红色的瓷砖；
3）‘@’：黑色的瓷砖，并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。
当在一行中读入的是两个零时，表示输入结束。
输出格式：
对每个数据集合，分别输出一行，显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。
数据范围：
1≤W,H≤20
输入样例：
6 9 ....#. .....# ...... ...... ...... ...... ...... #@...# .#..#. 0 0
输出样例：
45
思路分析
代码（dfs）
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 25; int n, m; char g[N][N]; bool st[N][N]; int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1}; int dfs(int x, int y) { int cnt = 1; 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>= m) continue; if (st[a][b]) continue; if (g[a][b] == '#') continue; cnt += dfs(a, b); } return cnt; } int main() { while (cin >> m >> n, n || m) { memset(st, false, sizeof st); 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] == '@') { printf("%d\n",dfs(i, j)); break; } } return 0; }
代码(bfs)
#include <iostream> #include <cstring> #include <algorithm> #include <queue> #define x first #define y second using namespace std; typedef pair<int, int> PII; const int N = 25; int n, m; char g[N][N]; int st[N][N]; int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1}; int bfs(int x, int y) { memset(st, false, sizeof st); queue<PII> q; q.push({x, y}); st[x][y] = true; int cnt = 1; while (q.size()) { auto t = q.front(); q.pop(); 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 (g[a][b] == '#') continue; if (st[a][b]) continue; st[a][b] = true; q.push({a, b}); cnt ++; } } return cnt; } int main() { while (cin >> m >> n, n || m) { 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] == '@') { printf("%d\n", bfs(i, j)); break; } } return 0; }
