grant's Blog

记录生活中的点点滴滴

蓝桥杯学习总结（十九）

发表于 更新于 分类于 ，   阅读次数： Valine：
本文字数： 4.2k 阅读时长 ≈ 4 分钟

2.2 acwing.1113. 红与黑（信息学奥赛一本通）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。
你站在其中一块黑色的瓷砖上，只能向相邻（上下左右四个方向）的黑色瓷砖移动。
请写一个程序，计算你总共能够到达多少块黑色的瓷砖。

输入格式
输入包括多个数据集合。
每个数据集合的第一行是两个整数 W 和 H，分别表示 x 方向和 y 方向瓷砖的数量。
在接下来的 H 行中，每行包括 W 个字符。每个字符表示一块瓷砖的颜色，规则如下
1）‘.’：黑色的瓷砖；
2）‘#’：红色的瓷砖；
3）‘@’：黑色的瓷砖，并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。
当在一行中读入的是两个零时，表示输入结束。

输出格式
对每个数据集合，分别输出一行，显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。

数据范围
1≤W,H≤20
输入样例：
6 9 
....#. 
.....# 
...... 
...... 
...... 
...... 
...... 
#@...# 
.#..#. 
0 0
输出样例：
45

思路：

考察Flood Fill（洪水灌溉）算法。

对于一个网格图，部分是陆地，部分是海洋，给定一个初始陆地块，找出它所在的连通块，用到上述算法。

可以用BFS和DFS实现，BFS可以求出最短距离，但是DFS用起来更方便一写，在某些情况下可能有爆栈风

险。

1.BFS算法

时间复杂度：O(W*H)。

BFS伪代码：

image-20210527111336765

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
const int N = 21;
int n,m;
char g[N][N];

int bfs(PII start){
    queue<PII> q;
    q.push(start);
    g[start.x][start.y] = '#';// 走过的格子标记为#

    int res = 0;
    int dx[] = {-1,0,1,0},dy[] = {0,1,0,-1};

    while (q.size()){
        auto t = q.front();
        q.pop();
        res++;// 每出队一个格子，答案+1
        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 || g[x][y] != '.') continue;
            g[x][y] = '#';// 走过的格子标记为#
            q.push({x,y});
        }
    }
    return res;
}
int main(){
    while (cin >> m >> n,n && m){
        PII start;
        // 对于g数组，因为下一个样例会读入新的数据将g数组覆盖，所以初始化可做可不做
        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] == '@') start = {i,j};// 可以break提前退出

        printf("%d\n",bfs(start));
    }
    return 0;
}

2.DFS算法

时间复杂度：O(W*H)。代码量比BFS稍短。

image-20210527131046394

DFS：从一个格子搜到底，然后回溯到上一层，继续搜到底，最后回溯到起点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;

const int N = 21;
char g[N][N];
int n,m;

int dx[] = {-1,0,1,0},dy[] = {0,1,0,-1};
int dfs(int x,int y){
    g[x][y] = '#';
    int res = 1;
    for (int i = 0;i < 4;i++){
        int xx = x+dx[i],yy = y+dy[i];
        if (xx >= 0 && xx < n && yy >= 0 && yy < m && g[xx][yy] == '.'){
            res += dfs(xx,yy);
        }
    }
    return res;
}

int main(){
    while (scanf("%d%d",&m,&n)){
        if (n == 0 && m == 0) break;
        
        for (int i = 0;i < n;i++) scanf("%s",g[i]);
         
        int x = 0,y = 0;
        for (int i = 0;i < n;i++)
            for (int j = 0;j < m;j++)
                if (g[i][j] == '@'){
                    x = i,y = j;
                    break;
                }
                
        printf("%d\n",dfs(x,y));
    }
    return 0;
}

3.图论

3.1 acwing.1224. 交换瓶子

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
有 N 个瓶子，编号 1∼N，放在架子上。
比如有 5 个瓶子：
2 1 3 5 4
要求每次拿起 2 个瓶子，交换它们的位置。
经过若干次后，使得瓶子的序号为：
1 2 3 4 5
对于这么简单的情况，显然，至少需要交换 2 次就可以复位。
如果瓶子更多呢？你可以通过编程来解决。

输入格式
第一行包含一个整数 N，表示瓶子数量。
第二行包含 N 个整数，表示瓶子目前的排列状况。

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

数据范围
1≤N≤10000,

输入样例1：
5
3 1 2 5 4
输出样例1：
3
输入样例2：
5
5 4 3 2 1
输出样例2：
2

思路：

算法1：暴力枚举，时间复杂度：O(n^2)

这道题是一道类似于模拟的题，实际思路就是遍历数位，发现和他应有顺序不同的，就从他后面（i+1->n)寻

找相同的，然后将二者交换，之后再往后遍历到n即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int a[N],n,t;
int ans=0;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=n;i++)
    {
        if(a[i]!=i)
        {
            for(int j=i+1;j<=n;j++)
            {
                if(a[j]==i)
                {
                    t=a[i];
                    a[i]=a[j];
                    a[j]=t;
                }
            }
            ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
} 

作者：田所浩二
链接：https://www.acwing.com/solution/content/6983/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

算法2：图论，时间复杂度：O(n)

把每个点都遍历一次，O(n)。

图片来源：https://www.acwing.com/solution/content/7917/。

image-20210527144519837

image-20210527144700090

一般来看：

情况1：交换同一个环内的点，会裂成两个环。

情况2：交换不同环内的点，会合成一个环。

下图是我手绘的。

image-20210527150734505

假设对于给定的瓶子顺序，构成k个环，我们把它们从小到大排列，一共是n个环，至少需要n-k次。

所以原问题就转化成了如何求环的数量k。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <cstdio>
#include <iostream>
using namespace std;

const int N = 1e4+10;

int n;
bool st[N];// 判重数组
int b[N];

int main(){
    scanf("%d",&n);
    // 下标从1开始，编号与位置统一
    for (int i = 1;i <= n;i++) scanf("%d",&b[i]);

    int cnt = 0;// 计算环的数量
    for (int i = 1;i <= n;i++)
        if (!st[i]){//如果没有标记过, 说明这个点在一个新的环中
            cnt ++;// 环数+1
            // 把这个点能到的所有点全部标记一下
            for (int j = i;!st[j];j = b[j])// 遍历环
                st[j] = true;
        }

    printf("%d\n",n-cnt);
    return 0;
}
坚持原创技术分享，您的支持将鼓励我继续创作！