蓝桥杯刷题笔记-搜索集合

ゞ浴缸里的玫瑰 2024-03-25 21:34 42阅读 0赞

### [迷宫][Link 1] ###

![b56685d9ff8faf53b11bbc15c2edf55d.png][]

#### 思路 ####

看到这道关于迷宫的题，脑海中立马浮现了BFS搜索，但是这道题在迷宫的基础上还增加了传送门，这道题需要我们求解的是从初始格子到终点的最短步数的期望值。而期望值是每一个格子到终点的最短路径/总的格子数。如果要求每个点到终点的最短路径，那就要bfs4000次，结果就会超时，所以我们直接从终点开始bfs一遍，就可以找出到各个点的最短路径。

二维数组映射小技巧：n行m列（i,j） 映射到一维的下标为**（i\*m+j）【下标从（0，0）开始】**

#### 代码 ####

import java.util.*;
 
 public class Main {
 static int n,m;
 static Map<Integer, List<int[]>> map = new HashMap<>();
 static boolean[][] st = new boolean[2010][2010];//标记是否访问这个点，防止再次遍历
 static int[] x={-1,0,1,0};
 static int[] y={0,1,0,-1};
 
 public static void main(String[] args) {
 Scanner sc = new Scanner(System.in);
 n = sc.nextInt();
 m = sc.nextInt();
 
 //把传送门加到图里
 for (int i = 0; i < m; i++) {
 int x1 = sc.nextInt() - 1;
 int y1 = sc.nextInt() - 1;
 int x2 = sc.nextInt() - 1;
 int y2 = sc.nextInt() - 1;
 add(x1, y1, x2, y2);
 add(x2, y2, x1, y1);
 }
 
 int ans = 0;//累计答案
 int c = 0; //计算层数
 Queue<int[]> queue = new LinkedList<>();
 queue.offer(new int[]{n - 1, n - 1}); //从终点开始找
 st[n - 1][n - 1] = true;
 while (!queue.isEmpty()) {
 int size = queue.size();
 
 while (size-- > 0) {//在这一层上进行操作
 int[] temp = queue.poll();
 int a = temp[0];
 int b = temp[1];
 ans += c;//累加答案
 
 //检查是否有传送门,有传送门就把传送门加进队列
 if (map.containsKey(a * n + b)) {
 List<int[]> list = map.get(a * n + b);
 for (int[] g : list) {
 if (!st[g[0]][g[1]]) {
 queue.offer(g);
 st[g[0]][g[1]] = true;
 }
 }
 }
 
 //走上下左右
 for (int i = 0; i < 4; i++) {
 int xx = a + x[i];
 int yy = b + y[i];
 if (xx >= 0 && xx < n && yy >= 0 && yy < n && !st[xx][yy]) {
 queue.offer(new int[]{xx, yy});
 st[xx][yy] = true;
 }
 }
 }
 c++;
 }
 System.out.printf("%.2f", ans * 1.0 / (n * n));
 }
 
 static void add(int i,int j,int x,int y){
 if(!map.containsKey(i*n+j)) map.put(i*n+j,new ArrayList<>());
 map.get(i*n+j).add(new int[]{x,y});
 }
 }

### [全球变暖][Link 2] ###

> **题目描述**  
> 你有一张某海域 *NxN* 像素的照片，"."表示海洋、"\#"表示陆地，如下所示：  
> .......  
> .\#\#....  
> .\#\#....  
> ....\#\#.  
> ..\#\#\#\#.  
> ...\#\#\#.  
> .......  
> 其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有 2 座岛屿。  
> 由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。  
> 例如上图中的海域未来会变成如下样子：  
> .......  
> .......  
> .......  
> .......  
> ....\#..  
> .......  
> .......  
> 请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。

#### 思路 ####

这就是一个求连通块的问题，求连通块我们一般会想到并查集。按照题目的意思，一个岛屿就是一个连通块，我们检查每一个连通块，如果连通块中有一个点上下左右都是\#，那就不会被淹没。

那么我们去遍历这个海域，以一个\#为切入点进行bfs全方位搜索，当找不到一个点上下左右全是\#时，就记录。把我们搜过的点标记，防止再次搜索。

#### 代码 ####

import java.util.LinkedList;
 import java.util.Queue;
 import java.util.Scanner;
 
 public class Main {
 static boolean[][] st;
 static int n;
 static int[] dx={-1,0,1,0};
 static int[] dy={0,1,0,-1};
 
 static boolean flag=false;
 
 public static void main(String[] args) {
 Scanner sc = new Scanner(System.in);
 n=sc.nextInt();
 char[][] arr=new char[n][n];
 for(int i=0; i<n; i++){
 arr[i]=sc.next().toCharArray();
 }
 st = new boolean[n][n];
 int ans=0;
 for(int i=0; i<n; i++){
 for(int j=0; j<n; j++){
 if(arr[i][j]=='#' && !st[i][j]) { //切入点
 Queue<int[]> queue = new LinkedList<>();
 queue.offer(new int[]{i, j});
 st[i][j] = true;
 bfs(arr, queue);
 if (!flag) ans++;
 flag = false;//这里不要忘了，每一次都要将flag重置为false
 }
 }
 }
 System.out.println(ans);
 }
 
 static void bfs(char[][] arr,Queue<int[]> queue){
 while (!queue.isEmpty()){
 int size=queue.size();
 while (size-->0){
 int[] curr=queue.poll();
 int a=curr[0];
 int b=curr[1];
 //这条件判断说明a是不会被淹没的陆地
 if(check(arr,a+dx[0],b+dy[0])&&check(arr,a+dx[1],b+dy[1])&&check(arr,a+dx[2],b+dy[2])&&check(arr,a+dx[3],b+dy[3])){
 flag=true;
 }
 
 //走上下左右
 for(int i=0; i<4; i++){
 int xx=a+dx[i];
 int yy=b+dy[i];
 if(arr[xx][yy]=='#'&&!st[xx][yy]){
 st[xx][yy]=true;
 queue.offer(new int[]{xx,yy});//这里加进队列去bfs判断山下左右是否为#
 }
 }
 }
 }
 }
 
 static boolean check(char[][] arr,int x,int y){
 return arr[x][y]=='#';
 }
 }

### [大胖子走迷宫][Link 3] ###

![6233d88774f4e46c212b27a5d35f918c.png][]

#### 思路 ####

一看到走迷宫，我们就又想到了bfs，找最短路。这道题需要注意的是小明的体重变化以及他可以停留在**原地不动**。那么什么时候小明会原地不动呢？当入口太窄而小明太胖过不去时，就只能原地等待到k或2k时刻变瘦之后才能走过去。我们用**tmp**表示小明的肥胖程度。当小明占用5\*5的方格时，他的肥胖程度就为2，也可以理解为偏移量，x,y的偏移量为2；同理，小明占用3\*3的方格时候，他的肥胖程度就为1；小明占用1\*1的方格时候，他的肥胖程度就为0。

一个小破图：

#### 代码 ####

import java.util.LinkedList;
 import java.util.Queue;
 import java.util.Scanner;
 
 public class Main {
 static int N=310;
 static char[][] arr = new char[N][N];
 static boolean[][] st = new boolean[N][N];
 static int[] dx={-1,0,1,0};
 static int[] dy={0,1,0,-1};
 static int tmp=2;//小明的肥胖程度
 
 public static void main(String[] args) {
 Scanner sc=new Scanner(System.in);
 int n=sc.nextInt();
 int k=sc.nextInt();
 for(int i=0; i<n; i++) {
 arr[i] = sc.next().toCharArray();
 }
 Queue<int[]> queue=new LinkedList<>();
 queue.offer(new int[]{2,2});
 st[2][2]=true;
 
 int cnt=0;//走的步数
 
 while (!queue.isEmpty()){
 int size=queue.size();
 while (size-- > 0){
 int[] curr=queue.poll();
 int x=curr[0];
 int y=curr[1];
 //判断是否到达终点
 if(x==n-3 && y==n-3){
 System.out.println(cnt);
 return;
 }
 
 //走上下左右
 for(int i=0; i<4; i++){
 int a=x+dx[i];
 int b=y+dy[i];
 //这里一定不要忘了判断是否遍历过 即st是false
 if(a-tmp>=0 && a+tmp<n && b-tmp>=0 && b+tmp<n && check(a,b) && !st[a][b]){
 queue.offer(new int[]{a,b});
 st[a][b]=true;
 }
 }
 //原地踏步，将a,b再一次加进去
 queue.offer(new int[]{x,y});
 }
 cnt++;
 if(cnt==k) tmp=1;
 if(cnt==2*k) tmp=0;
 }
 }
 
 static boolean check(int a, int b) {
 //遍历这个矩阵
 for (int i = a - tmp; i <= a + tmp; i++) {
 for (int j = b - tmp; j <= b + tmp; j++) {
 if (arr[i][j] == '*') return false;
 }
 }
 return true;
 }
 }

### [分考场][Link 4] ###

![146264ed886b807bce7b663ae6429ee4.png][]

#### 思路 ####

这道分考场的题目，我们先来分析一下，每个人有两种选择，第一种：加入已有的考场，第二种：给他安排一个新的考场。用map存储判断两人是否在同一个考场，如果map为true表示在一个考场。直接用dfs暴力搜索。

#### 代码 ####

import java.util.*;
 
 public class Main {
 static int n, m, N = 110;
 static List<Integer>[] list = new ArrayList[N];
 static int ans = 100;
 static boolean[][] map = new boolean[N][N];
 
 public static void main(String[] args) {
 Scanner sc = new Scanner(System.in);
 n = sc.nextInt();
 m = sc.nextInt();
 for (int i = 0; i < m; i++) {
 int a = sc.nextInt();
 int b = sc.nextInt();
 map[a][b] = map[b][a] = true;
 }
 for (int i = 1; i <= n; i++) {
 list[i] = new ArrayList<>();
 }
 dfs(1, 0);
 System.out.println(ans);
 }
 
 //st是学生，cl是教室数量
 static void dfs(int st, int cl) {
 //减枝 把一些一定不可能是答案的情况排除掉
 if (cl >= ans) return;
 //说明已经把所有的学生都安排好了
 if (st > n) {
 ans = cl;
 return;
 }
 for (int i = 1; i <= cl; i++) {
 int j = 0;
 //看第i号教室的人和当前的同学st是否冲突
 for (; j < list[i].size(); ++j) {
 if (map[st][list[i].get(j)]) break;
 }
 //说明和这个教室全部学生都不相等
 if (j == list[i].size()) {
 list[i].add(st);
 dfs(st + 1, cl);
 //回溯
 list[i].remove(list[i].size() - 1);
 }
 }
 //走到这步还没找到教室说明需要新教室
 list[cl + 1].add(st);
 dfs(st + 1, cl + 1);
 list[cl + 1].remove(list[cl + 1].size() - 1);
 }
 }

[Link 1]: https://www.lanqiao.cn/problems/2222/learning/?page=1&first_category_id=1&sort=students_count&second_category_id=3&name=%E8%BF%B7%E5%AE%AB
[b56685d9ff8faf53b11bbc15c2edf55d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/2ec639066ce94cbfb01de942c511f30d.png
[Link 2]: https://www.lanqiao.cn/courses/11020/learning/?id=789496
[Link 3]: https://www.lanqiao.cn/courses/11020/learning/?id=789497&compatibility=false
[6233d88774f4e46c212b27a5d35f918c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/2dc977b2d9b94ea197cc690e38bb9188.png
[Link 4]: https://www.lanqiao.cn/courses/11020/learning/?id=789498&compatibility=false
[146264ed886b807bce7b663ae6429ee4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/afe6b45f8cbc4a72ae5a2da647e29b35.png