前言

蓝桥杯官网：蓝桥杯大赛——全国大学生TMT行业赛事
✨本博客讲解 蓝桥杯C/C++ 备赛所涉及算法知识，此博客为第十二讲：图论【例题】

本篇博客所包含习题有：
👊献给阿尔吉侬的花束
👊红与黑
👊交换瓶子

图论【习题】见博客：蓝桥杯第十二讲–图论【习题】
$BFS$、$DFS$ 算法模板见博客：树与图的遍历：DFS，BFS 算法模板
$BFS$ 知识讲解见博客：BFS

博客内容以题代讲，通过讲解题目的做法来帮助读者快速理解算法内容，需要注意：学习算法不能光过脑，更要实践，请读者务必自己敲写一遍本博客相关代码！！！

献给阿尔吉侬的花束

题目要求

题目描述：

阿尔吉侬是一只聪明又慵懒的小白鼠，它最擅长的就是走各种各样的迷宫。

今天它要挑战一个非常大的迷宫，研究员们为了鼓励阿尔吉侬尽快到达终点，就在终点放了一块阿尔吉侬最喜欢的奶酪。

现在研究员们想知道，如果阿尔吉侬足够聪明，它最少需要多少时间就能吃到奶酪。

迷宫用一个 $R\times C$ 的字符矩阵来表示。

字符 $S$ 表示阿尔吉侬所在的位置，字符 $E$ 表示奶酪所在的位置，字符 $\#$ 表示墙壁，字符 $.$ 表示可以通行。

阿尔吉侬在 $1$ 个单位时间内可以从当前的位置走到它上下左右四个方向上的任意一个位置，但不能走出地图边界。

输入格式：

第一行是一个正整数 $T$，表示一共有 $T$ 组数据。

每一组数据的第一行包含了两个用空格分开的正整数 $R$ 和 $C$，表示地图是一个 $R\times C$ 的矩阵。

接下来的 $R$ 行描述了地图的具体内容，每一行包含了 $C$ 个字符。字符含义如题目描述中所述。保证有且仅有一个 $S$ 和 $E$。

输出格式：

对于每一组数据，输出阿尔吉侬吃到奶酪的最少单位时间。

若阿尔吉侬无法吃到奶酪，则输出“oop!”（只输出引号里面的内容，不输出引号）。

每组数据的输出结果占一行。

数据范围：

$1<T\le 10,$
$2\le R,C\le 200$

输入样例：

3
3 4
.S..
\#\#\#\.
..E.
3 4
.S..
.E..
....
3 4
.S..
\#\#\#\#
..E.

输出样例：

5
1
oop!

思路分析

一个典型的 $bfs$ 问题，对于 $bfs$ 类问题，我们需要使用一个辅助队列，可以使用 $STL$ 中的 $queue$，使用方法见博客：STL—queue，当然你也可以手写队列，见博客：数组模拟队列，手写队列要比调用 $queue$ 略快一点。关于定义偏移量的问题，我们在博客：蓝桥杯第二讲–递推【例题】 也有讲解，这是必须掌握的知识点。

代码

#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\le W,H\le 20$

输入样例：

6 9 
....#. 
.....# 
...... 
...... 
...... 
...... 
...... 
#@...# 
.#..#. 
0 0

输出样例：

45

思路分析

本题其实是属于 $Flood$ $Fill$ 类问题，说白了就是 $bfs$，$dfs$ 类问题，关于 $Flood$ $Fill$ 算法，见博客：Flood Fill，$Flood$ $Fill$ 算法其实用 $dfs$ 或者 $bfs$ 都可以进行解决，一般情况下，$dfs$ 的代码量要小于 $bfs$，但是 $dfs$ 容易爆栈，在这道题中，$dfs$ 和 $bfs$ 都可以做，下面给出两个代码供读者理解。

代码 $(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;
}

交换瓶子

来源： 第七届蓝桥杯省赛C++B组,第七届蓝桥杯省赛JAVAA组

题目要求

题目描述：

有 $N$ 个瓶子，编号 $1$∼$N$，放在架子上。

比如有 $5$ 个瓶子：

2 1 3 5 4

要求每次拿起 $2$ 个瓶子，交换它们的位置。

经过若干次后，使得瓶子的序号为：

1 2 3 4 5

对于这么简单的情况，显然，至少需要交换 $2$ 次就可以复位。

如果瓶子更多呢？你可以通过编程来解决。

输入格式：

第一行包含一个整数 $N$，表示瓶子数量。

第二行包含 $N$ 个整数，表示瓶子目前的排列状况。

输出格式：

输出一个正整数，表示至少交换多少次，才能完成排序。

数据范围：

$1\le N\le 10000$

输入样例1：

5
3 1 2 5 4

输出样例1：

3

输入样例2：

5
5 4 3 2 1

输出样例2：

2

思路分析

不愧是暴力杯，其实本题的优化是比较复杂的，但是妙就妙在本题的暴力法居然是可以打满分的，关于暴力的代码不做过多解释，就是遍历两遍数组，在对的位置进行交换即可，本题的优化的思路建议读者好好动手思考，运用了离散数学的相关知识，下面进行讲解：

我们来把这个问题以一种特殊的切入点进行思考：
拿例子来说明：

样例1：
3 1 2 5 4
目标：
1 2 3 4 5

我们按照对应关系进行建图：$3$号瓶子现在处于位置$1$ 上，当前位置$3$ 上是 $2$号瓶子，所以我们从 $3$ 到 $2$ 连一条有向边：

同理，当前 $2$号瓶子在 位置$3$ 上，它应该在位置$2$ 上，当前位置$2$ 上是 $1$号瓶子，故从 $2$ 到 $1$ 连一条有向边：

按照上述说法，读者自行对样例1进行建图，结果如下图所示：

现在我们来交换 $1$号瓶子和 $3$号瓶子，即我们变成了：

```cpp
样例1：
1 3 2 5 4
目标：
1 2 3 4 5

重复上述建图：

可以看出，交换一个环的元素的结果就是把一个环拆成了两个环，那么交换两个环的元素，其实就是让两个环进行了合并操作：可以理解成上述操作的逆操作。

而我们最终想要得到的，其实就是让 $1,2,3,4,5$ 分别独立成环，即我们要对一个环内的元素进行不断交换：让一个大环不断的拆分为两个小环，直到每个环均只有一个元素。

所以本题就变成了求一开始有多少个环，即最初的 $n$ 个元素是几个环，假设初始值有 $cnt$ 个环，我们只需要输出 $n-cnt$ 即可，因为想要把一个环拆分成$n$个元素，我们需要砍 $n-1$ 刀，我们可以理解为：一开始题目已经帮助我们分成了 $cnt$ 个环，即我们少操作了 $cnt$ 次，故我们最终只需要输出 $n-cnt$ 即可。

代码 (暴力)

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10010;

int b[N];

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> b[i];
    
    int cnt = 0;
    for (int i = 1; i <= n; i ++ )
        if (b[i] != i)
            for (int j = 1; j <= n; j ++ )
                if (b[j] == i)
                {
                    swap(b[j], b[i]);
                    cnt ++;
                    break;
                }
    
    cout << cnt << endl;
    
    return 0;
} 

代码 (置换群)

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10010;

int b[N];
bool st[N];

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> b[i];

    int cnt = 0;
    for (int i = 1; i <= n; i ++ )
        if (!st[i])
        {
            cnt ++;
            for (int j = i; !st[j]; j = b[j])
                st[j] = true;
        }

    cout << n - cnt << endl;

    return 0;
}

文章来源: chen-ac.blog.csdn.net，作者：辰chen，版权归原作者所有，如需转载，请联系作者。

原文链接：chen-ac.blog.csdn.net/article/details/122793291