[蓝桥杯] 双指针、BFS和DFS与图论问题

 

文章目录

一、日志统计

1、1 题目描述

1、2 题解关键思路与解答

二、献给阿尔吉侬的花束

2、1 题目描述

2、2 题解关键思路与解答

三、红与黑

3、1 题目描述

3、2 题解关键思路与解答

3、2、1 dfs题解代码

3、2、2 bfs题解答案

四、交换瓶子

4、1 题目描述

4、2 题解关键思路与解答

---

  本篇文章针对蓝桥杯比赛的考点，列出双指针、BFS和DFS与图论的相关习题以及知识点的解释。希望本篇文章会对你有所帮助。

一、日志统计

1、1 题目描述

题目来源：第九届蓝桥杯省赛C++B组,第九届蓝桥杯省赛JAVAB组

题目难度：简单

题目描述：小明维护着一个程序员论坛。现在他收集了一份”点赞”日志，日志共有 N 行。

其中每一行的格式是：

ts id  

  表示在 ts 时刻编号 id 的帖子收到一个”赞”。现在小明想统计有哪些帖子曾经是”热帖”。如果一个帖子曾在任意一个长度为 D 的时间段内收到不少于 K 个赞，小明就认为这个帖子曾是”热帖”。

  具体来说，如果存在某个时刻 T 满足该帖在 [T,T+D) 这段时间内(注意是左闭右开区间)收到不少于 K 个赞，该帖就曾是”热帖”。给定日志，请你帮助小明统计出所有曾是”热帖”的帖子编号。

输入格式：

  第一行包含三个整数 N,D,K。

  以下 N 行每行一条日志，包含两个整数 ts 和 id。

输出格式：

  按从小到大的顺序输出热帖 id。

  每个 id 占一行。

数据范围：

  1≤K≤N≤1e5,
  0≤ts,id≤1e5,
  1≤D≤10000。

输入样例：

7 10 2
0 1
0 10
10 10
10 1
9 1
100 3
100 3

输出样例：

1
3

1、2 题解关键思路与解答

  我们大概叙述一下题目的意思：在一段时间内某个帖子的赞达到一定数量就被称为热帖。这道题中关键的就去维护一段时间段，看这个时间段内该帖子是否达到一定能够赞数。这个时候我们就需要两个指针（并不是真正的指针，是指变量）来维护这个时间段的区间了。我们先去要对输入的时间进行一个排序，然后再去维护这个区间，开一个记录状态的数组去看是否有达到热帖的。我们结合着代码一起理解一下：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>#define x first
#define y secondusing namespace std;typedef pair<int,int> PII;const int N=1e5+10;PII q[N];
int cnt[N];
bool st[N];int n,d,k;
int main()
{scanf("%d%d%d", &n, &d, &k);for(int i=0;i<n;i++)scanf("%d%d",&q[i].x,&q[i].y);sort(q,q+n);for(int i=0,j=0;i<n;i++){int id=q[i].y;cnt[id]++;//时间段区间while(q[i].x-q[j].x>=d){cnt[q[j].y]--;j++;}if(cnt[id]>=k)st[id]=true;}for(int i=0;i<N;i++)if(st[i])printf("%d\n",i);return 0;
}

二、献给阿尔吉侬的花束

2、1 题目描述

题目来源：《信息学奥赛一本通》

题目难度：简单

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

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

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

迷宫用一个 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!

2、2 题解关键思路与解答

  首先我们要住注意的是本题的输入格式，要注意的是输入 0 0 时结束。我们要找到开始的位置和奶酪的位置。我们需要从开始位置出发，且是最小路径到达奶酪位置。这时我们可以想到洪水灌溉法（Flood Fill）。洪水灌溉法是指：dfs（深度优先搜索）和 bfs（宽度优先搜索）。dfs是采用递归的方法不断实现覆盖。dfs与bfs又有所不同，dfs写起来代码简单，bfs可以求出最短路径，各有优势。宽度优先是一层一层进行遍历的。是用队列进行维护实现的。队列是先进先出的原则。我们先把第一个数据入队。然后再循环进行维护。除去对头，入队与对头相关的点，直到队列为空。bfs有固定模板，通过本题，我们可以进行记一下。我们结合代码理解一下：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>using namespace std;#define x first
#define y secondtypedef pair<int,int> PII;const int N=210;int n,m;int dist[N][N];
char g[N][N];int bfs(PII start,PII end)
{queue<PII> q;memset(dist,-1,sizeof dist); //初始dsit为-1，表示为没有走过该点dist[start.x][start.y]=0;q.push(start);while(q.size()){PII t=q.front();q.pop();int dx[4]={-1,1,0,0},dy[4]={0,0,-1,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)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;cin>>T;while(T--){scanf("%d%d",&n,&m);for(int i=0;i<n;i++)scanf("%s",g[i]);PII start,end;for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(g[i][j]=='S')start={i,j};else if(g[i][j]=='E')end={i,j};int distance=bfs(start,end);if(distance==-1)puts("oop!");elseprintf("%d\n",distance);}return 0;
}

三、红与黑

3、1 题目描述

题目来源：《信息学奥赛一本通》

题目难度：简单

题目描述：有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上，只能向相邻（上下左右四个方向）的黑色瓷砖移动。请写一个程序，计算你总共能够到达多少块黑色的瓷砖。

输入格式：

  输入包括多个数据集合。每个数据集合的第一行是两个整数 W 和 H，分别表示 x 方向和 y 方向瓷砖的数量。

  在接下来的 H 行中，每行包括 W 个字符。每个字符表示一块瓷砖的颜色，规则如下

  （1）‘.’：黑色的瓷砖；
  （2）‘#’：红色的瓷砖；
  （3）‘@’：黑色的瓷砖，并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。

  当在一行中读入的是两个零时，表示输入结束。

输出格式：

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

数据范围：

1≤W,H≤20。

输入样例：

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

输出样例：

45

3、2 题解关键思路与解答

  该题我们就可以用dfs，也可以用bfs进行解答。但是用dfs时，我们要注意的是我们不需要有回复现场的操作，与第十四届蓝桥杯第三期模拟赛 C/C++ B组 原题与详解 填空题中的最大连通块类似。这道题目每个格子是一个状态，每个格子只会搜索一次，所以不需要恢复现场。我们分别看一下dfs与bfs的解题代码：

3、2、1 dfs题解代码

#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;const int N = 25;int n, m;
char g[N][N];
bool st[N][N];int dx[4] = {-1, 0, 1, 0}, dy[4] = {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 (g[a][b] != '.') continue;if (st[a][b]) continue;cnt += dfs(a, b);}return cnt;
}int main()
{while (cin >> m >> n, n || m){for (int i = 0; i < n; i ++ ) cin >> g[i];int x, y;for (int i = 0; i < n; i ++ )for (int j = 0; j < m; j ++ )if (g[i][j] == '@'){x = i;y = j;}memset(st, 0, sizeof st);cout << dfs(x, y) << endl;}return 0;
}

3、2、2 bfs题解答案

#include<bits/stdc++.h>using namespace std;#define x first
#define y secondconst int N =25;typedef pair<int,int> PII;char g[N][N];int n,m;int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};int bfs(int x,int y)
{queue<PII> q;q.push({x,y});g[x][y]='#';int res=0;while(q.size()){PII t=q.front();q.pop();res++;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;q.push({a,b});g[a][b]='#';}   }return res;
}
int main()
{while(cin>>m>>n,n||m){for(int i=0;i<n;i++)cin>>g[i];int x,y;for(int i=0;i<n;i++)for(int j=0;j<m;j++){if(g[i][j]=='@'){x=i;y=j;}}cout<<bfs(x,y)<<endl;}return 0;
}

四、交换瓶子

4、1 题目描述

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

题目难度：简单

题目描述：有 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

4、2 题解关键思路与解答

   本题用到了图论的相关知识。我们把每个位置对应瓶子的编号进行连接，会形成相应的环。我们看题目中的例1：

   我们需要做的是形成5个环，也就是自己指向自己。我们发先对一个含有两个及以上元素的环进行元素交换操作，一个环就会变成两个环。初始环越多，我们需要操作的次序越少，因为环中的元素很少。假如一个环中的元素有5个，我们最少的步数为4次。这样我们总结出规律是：最少需要操作的部数=元素个数-环的个数。我们看代码：

#include<iostream>
#include<algorithm>
#include<cstring>using namespace std;const int N=1e4+10;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;
}