第十四届蓝桥杯三月真题刷题训练——第 19 天
第 1 题：灌溉_BFS板子题
题目描述
小蓝负责花园的灌溉工作。
花园可以看成一个 n 行 m 列的方格图形。中间有一部分位置上安装有出水管。
小蓝可以控制一个按钮同时打开所有的出水管，打开时，有出水管的位置可以被认为已经灌溉好。
每经过一分钟，水就会向四面扩展一个方格，被扩展到的方格可以被认为已经灌溉好。即如果前一分钟某一个方格被灌溉好，则下一分钟它上下左右的四个方格也被灌溉好。
给定花园水管的位置，请问 k 分钟后，有多少个方格被灌溉好？
输入描述
输入的第一行包含两个整数 n,m。
第二行包含一个整数 t，表示出水管的数量。
接下来 t 行描述出水管的位置，其中第 i 行包含两个数 r,c 表示第 r 行第 c 列有一个排水管。
接下来一行包含一个整数 kk。
其中，1≤n,m≤100,1≤t≤10,1≤k≤100。
输出描述
输出一个整数，表示答案。
输入输出样例
示例 1
输入
3 6 2 2 2 3 4 1输出
9运行限制
- 最大运行时间：1s
- 最大运行内存: 128M
代码：
package 第十四届蓝桥杯三月真题刷题训练.day19;
import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
/**
* @author yx
* @date 2023-03-22 8:29
*/
public class 灌溉_BFS模板题 {
static int[] X = {0, 0, -1, 1};
static int[] Y = {1, -1, 0, 0};
static int[][] map;
static int ans=0;//最后的输出答案
static PrintWriter out = new PrintWriter(System.out);
static BufferedReader ins = new BufferedReader(new InputStreamReader(System.in));
static StreamTokenizer in = new StreamTokenizer(ins);
/**
* 输入
* in.nextToken()
* int a= (int)in.nval;
* <p>
* 输出
* out.print();
* out.flush();
* <p>
* 读文件：
* BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("C:\\Users\\yx\\Desktop\\primes.txt")));
* String s = br.readLine();s读取每一行数据
* if (s == null)break;读取文件终止的语句
**/
public static void main(String[] args) throws IOException {
in.nextToken();
int n = (int) in.nval;
in.nextToken();
int m = (int) in.nval;
in.nextToken();
int t = (int) in.nval;
//初始就有t个出水点
ans=t;
//存储出水管的（x,y）
int[][] XY = new int[t][2];
for (int i = 0; i < 2; i++) {
String[] sp = ins.readLine().split(" ");
XY[i][0] = Integer.parseInt(sp[0]);
XY[i][1] = Integer.parseInt(sp[1]);
}
in.nextToken();
int k = (int) in.nval;
map = new int[n][m];
//队列
Queue<int[]> queue = new LinkedList<>();
//对方格进行初始化
for (int i = 0; i < t; i++) {
map[XY[i][0] - 1][XY[i][1] - 1] = 1;
//把洒水点入队
queue.offer(new int[]{XY[i][0] - 1, XY[i][1] - 1});
}
//不能超出k次循环且队列不为空
while (k > 0 && !queue.isEmpty()) {
//k分钟,一个循环消耗一分钟
k--;
int length = queue.size();
for (int i = 0; i < length; i++) {
//出队
int[] nums = queue.poll();
int x = nums[0];
int y = nums[1];
//遍历四个方向
for (int j = 0; j < 4; j++) {
int newX = x + X[j];
int newY = y + Y[j];
//m行n列
if (newX < n && newX >= 0 && newY < m && newY >= 0) {
if(map[newX][newY]==0){//表示当前位置没有洒水
ans++;
map[newX][newY]=1;//对该位置赋值
//把新洒水的位置入队
queue.offer(new int[]{newX,newY});
}
}
}
}
}
out.println(ans);
out.flush();
}
}
解析：
（1）这一题是一道经典的BFS板子题，几乎不需要对板子改变什么
（2）讲一下BFS搜索的几个要点：
- 初始化的一个二维数组Map
- 使用队列这一数据结构，将搜过的“老点”出队，将初始的“新点”入队
- 创建初始数组X={0，0，-1，1}，Y={1，-1，0，0}，每个点都要遍历一遍这个数组，表示可以往上下左右四个方向进行搜索
- 对新点要进行特判（数组越界、是否搜过....)这两个特判条件是最基本的，其它条件因题而异，比如可能会更加复杂一点（是否有障碍物......）
第 2 题：小朋友崇拜圈_暴搜
题目描述
班里 N 个小朋友，每个人都有自己最崇拜的一个小朋友（也可以是自己）。
在一个游戏中，需要小朋友坐一个圈，每个小朋友都有自己最崇拜的小朋友在他的右手边。
求满足条件的圈最大多少人？
小朋友编号为 1,2,3,⋯N。
输入描述
输入第一行，一个整数 N（3<N<10^5）。
接下来一行 N 个整数，由空格分开。
输出描述
要求输出一个整数，表示满足条件的最大圈的人数。
输入输出样例
示例
输入
9 3 4 2 5 3 8 4 6 9输出
4样例解释
如下图所示，崇拜关系用箭头表示，红色表示不在圈中。
显然，最大圈是[2 4 5 3] 构成的圈。
运行限制
- 最大运行时间：1s
- 最大运行内存: 256M
代码：
package 第十四届蓝桥杯三月真题刷题训练.day19;
import java.io.*;
/**
* @author yx
* @date 2023-03-22 9:46
*/
public class 小朋友崇拜圈_爆搜 {
static int[] nums;
static int max=0;
static int N;
static PrintWriter out =new PrintWriter(System.out);
static BufferedReader ins=new BufferedReader(new InputStreamReader(System.in));
static StreamTokenizer in=new StreamTokenizer(ins);
/**
* 输入
* in.nextToken()
* int a= (int)in.nval;
*
* 输出
* out.print();
* out.flush();
*
* 读文件：
* BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("C:\\Users\\yx\\Desktop\\primes.txt")));
* String s = br.readLine();s读取每一行数据
* if (s == null)break;读取文件终止的语句
**/
public static void main(String[] args) throws IOException {
in.nextToken();
N=(int) in.nval;
nums=new int[N+1];
//初始化数据
for (int i = 1; i <= N; i++) {
in.nextToken();
nums[i]=(int) in.nval;
}
for (int i = 1; i <= N; i++) {
int length=dfs(i);
if(max<length){
max=length;
}
}
out.println(max);
out.flush();
}
static int dfs(int i){
//初始往下走一个位置
int key=nums[i];
int length=1;
//往下爆搜，直到起点等于终点为止
while (key!=i){
key=nums[key];
length++;
//进入死环，返回0
if(length>N){
return 0;
}
}
return length;
}
}
解析：
（1）首先我们先对数组进行初始化，每个数组里面的存储的是对应下标学号的偶像
（比如：nums[1]=3,表示学号为1的同学崇拜的对象是学号为3的对象）
（2）其次我们遍历每一个数组元素，对其进行爆搜，此时我们需要注意一种死环的情况，比如1-->2-->3-->2-->3......一直在2和3之间绕圈圈，并且这个时候1，2，3并不能构成一个环，并且无限死循环下去，所以针对这个我们要特判一下，就这个行代码
//进入死环，返回0 if(length>N){ return 0; }