南部县网站建设,2万块建一个网站贵吗,商城源码下载,什么是网站的原型第 1 题#xff1a;灌溉_BFS板子题 题目描述 小蓝负责花园的灌溉工作。 花园可以看成一个 n 行 m 列的方格图形。中间有一部分位置上安装有出水管。 小蓝可以控制一个按钮同时打开所有的出水管#xff0c;打开时#xff0c;有出水管的位置可以被认为已经灌溉好。 每经过一分…第 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 ans0;//最后的输出答案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个出水点anst;//存储出水管的x,yint[][] 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];//队列Queueint[] 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{00-11}Y{1-100}每个点都要遍历一遍这个数组表示可以往上下左右四个方向进行搜索对新点要进行特判数组越界、是否搜过....)这两个特判条件是最基本的其它条件因题而异比如可能会更加复杂一点是否有障碍物......第 2 题小朋友崇拜圈_暴搜 题目描述 班里 N 个小朋友每个人都有自己最崇拜的一个小朋友也可以是自己。 在一个游戏中需要小朋友坐一个圈每个小朋友都有自己最崇拜的小朋友在他的右手边。 求满足条件的圈最大多少人 小朋友编号为 1,2,3,⋯N。 输入描述 输入第一行一个整数 N3N10^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 max0;static int N;static PrintWriter out new PrintWriter(System.out);static BufferedReader insnew BufferedReader(new InputStreamReader(System.in));static StreamTokenizer innew 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;numsnew int[N1];//初始化数据for (int i 1; i N; i) {in.nextToken();nums[i](int) in.nval;}for (int i 1; i N; i) {int lengthdfs(i);if(maxlength){maxlength;}}out.println(max);out.flush();}static int dfs(int i){//初始往下走一个位置int keynums[i];int length1;//往下爆搜直到起点等于终点为止while (key!i){keynums[key];length;//进入死环返回0if(lengthN){return 0;}}return length;}
}解析 1首先我们先对数组进行初始化每个数组里面的存储的是对应下标学号的偶像 比如nums[1]3,表示学号为1的同学崇拜的对象是学号为3的对象 2其次我们遍历每一个数组元素对其进行爆搜此时我们需要注意一种死环的情况比如1--2--3--2--3......一直在2和3之间绕圈圈并且这个时候123并不能构成一个环并且无限死循环下去所以针对这个我们要特判一下就这个行代码 //进入死环返回0
if(lengthN){
return 0;} 第 3 题括号序列 第 4 题砍竹子
