湖南新能源公司中企動力網(wǎng)站建設com天堂網(wǎng)
第 1 題：灌溉_BFS板子題
題目描述
小藍負責花園的灌溉工作。
花園可以看成一個 n 行 m 列的方格圖形。中間有一部分位置上安裝有出水管。
小藍可以控制一個按鈕同時打開所有的出水管，打開時，有出水管的位置可以被認為已經(jīng)灌溉好。
每經(jīng)過一分鐘，水就會向四面擴展一個方格，被擴展到的方格可以被認為已經(jīng)灌溉好。即如果前一分鐘某一個方格被灌溉好，則下一分鐘它上下左右的四個方格也被灌溉好。
給定花園水管的位置，請問 k 分鐘后，有多少個方格被灌溉好？
輸入描述
輸入的第一行包含兩個整數(shù) n,m。
第二行包含一個整數(shù) t，表示出水管的數(shù)量。
接下來 t 行描述出水管的位置，其中第 i 行包含兩個數(shù) r,c 表示第 r 行第 c 列有一個排水管。
接下來一行包含一個整數(shù) kk。
其中，1≤n,m≤100,1≤t≤10,1≤k≤100。
輸出描述
輸出一個整數(shù)，表示答案。
輸入輸出樣例
示例 1
輸入
3 6 2 2 2 3 4 1輸出
9運行限制
- 最大運行時間：1s
- 最大運行內(nèi)存: 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讀取每一行數(shù)據(jù)* 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次循環(huán)且隊列不為空while (k > 0 && !queue.isEmpty()) {//k分鐘,一個循環(huán)消耗一分鐘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){//表示當前位置沒有灑水a(chǎn)ns++;map[newX][newY]=1;//對該位置賦值//把新灑水的位置入隊queue.offer(new int[]{newX,newY});}}}}}out.println(ans);out.flush();}
}
解析：
（1）這一題是一道經(jīng)典的BFS板子題，幾乎不需要對板子改變什么
（2）講一下BFS搜索的幾個要點：
- 初始化的一個二維數(shù)組Map
- 使用隊列這一數(shù)據(jù)結(jié)構(gòu)，將搜過的“老點”出隊，將初始的“新點”入隊
- 創(chuàng)建初始數(shù)組X={0，0，-1，1}，Y={1，-1，0，0}，每個點都要遍歷一遍這個數(shù)組，表示可以往上下左右四個方向進行搜索
- 對新點要進行特判（數(shù)組越界、是否搜過....)這兩個特判條件是最基本的，其它條件因題而異，比如可能會更加復雜一點（是否有障礙物......）
第 2 題：小朋友崇拜圈_暴搜
題目描述
班里 N 個小朋友，每個人都有自己最崇拜的一個小朋友（也可以是自己）。
在一個游戲中，需要小朋友坐一個圈，每個小朋友都有自己最崇拜的小朋友在他的右手邊。
求滿足條件的圈最大多少人？
小朋友編號為 1,2,3,?N。
輸入描述
輸入第一行，一個整數(shù) N（3<N<10^5）。
接下來一行 N 個整數(shù)，由空格分開。
輸出描述
要求輸出一個整數(shù)，表示滿足條件的最大圈的人數(shù)。
輸入輸出樣例
示例
輸入
9 3 4 2 5 3 8 4 6 9輸出
4樣例解釋
如下圖所示，崇拜關(guān)系用箭頭表示，紅色表示不在圈中。
顯然，最大圈是[2 4 5 3] 構(gòu)成的圈。
運行限制
- 最大運行時間：1s
- 最大運行內(nèi)存: 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讀取每一行數(shù)據(jù)* if (s == null)break;讀取文件終止的語句**/public static void main(String[] args) throws IOException {in.nextToken();N=(int) in.nval;nums=new int[N+1];//初始化數(shù)據(jù)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++;//進入死環(huán)，返回0if(length>N){return 0;}}return length;}
}
解析：
（1）首先我們先對數(shù)組進行初始化，每個數(shù)組里面的存儲的是對應下標學號的偶像
（比如：nums[1]=3,表示學號為1的同學崇拜的對象是學號為3的對象）
（2）其次我們遍歷每一個數(shù)組元素，對其進行爆搜，此時我們需要注意一種死環(huán)的情況，比如1-->2-->3-->2-->3......一直在2和3之間繞圈圈，并且這個時候1，2，3并不能構(gòu)成一個環(huán)，并且無限死循環(huán)下去，所以針對這個我們要特判一下，就這個行代碼
//進入死環(huán)，返回0 if(length>N){ return 0;}