首页 > 编程语言 >蓝桥杯算法集训 - Week 4：BFS、并查集、Flood Fill、哈希、单调栈/队列

蓝桥杯算法集训 - Week 4：BFS、并查集、Flood Fill、哈希、单调栈/队列

时间：2024-03-25 20:01:12浏览次数：19  
标签：Week BFS ps int 蓝桥 ++ static && new

蓝桥杯算法集训 - Week 4

本系列随笔用于整理AcWing题单——《蓝桥杯集训·每日一题2024》的系列题型及其对应的算法模板。

一、BFS

BFS算法复习参考：BFS (Java) 广度优先搜索 简单介绍、模板、案例（一）

Ⅰ、代码模板

static void bfs(T root) {
    // 双端队列，用来存储元素
    Deque<T> queue = new ArrayDeque<>();
    // 添加首个元素
    queue.add(root);
    // 当队列不为空一直进行循环，直到队列不再有元素
    while(!queue.isEmpty()){
        int n = queue.size();
        
        for(int i = 0; i < n; i++){
            var t = queue.poll();

            // 在同一层的操作
            // ...
        }
        // 在非同层更新答案   
    }
}

Ⅱ、母亲的牛奶

1355. 母亲的牛奶 - AcWing题库

母亲的牛奶

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static final int N = 25;
	static int abc[] = new int[3];

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		for (int i = 0; i < 3; i++) {
			abc[i] = sc.nextInt();
		}
		sc.close();

		boolean used[][][] = new boolean[N][N][N];
		used[0][0][abc[2]] = true;
		
		Queue<int[]> q = new LinkedList<>();
		q.add(new int[] { 0, 0, abc[2] });
		while (!q.isEmpty()) {
			int[] a = q.poll();
			// 从i往j里到牛奶
			for (int i = 0; i < abc.length; i++) {
				for (int j = 0; j < abc.length; j++) {
					if (i != j) {
						int[] t = a.clone();
						if (t[i] + t[j] <= abc[j]) {
							t[j] += t[i];
							t[i] = 0;
						} else {
							t[i] -= abc[j] - t[j];
							t[j] = abc[j];
						}

						if (!used[t[0]][t[1]][t[2]]) {
							used[t[0]][t[1]][t[2]] = true;
							q.add(t);
						}
					}
				}
			}
		}

		for (int i = 0; i <= 20; i++) {
			boolean flag = false;
			for (int j = 0; j <= 20; j++) {
				if (used[0][j][i]) {
					flag = true;
					break;
				}
			}
			if (flag)
				System.out.print(i + " ");
		}
	}
}

二、并查集

并查集算法复习参考：【算法与数据结构】—— 并查集

Ⅰ、代码模板

// 存储每个点的祖宗节点
static int[] ps = new int[N];

// 返回 x 的祖宗节点
static int find(int x) {
	if (ps[x] != x)
		ps[x] = find(ps[x]);
	return ps[x];
}

// 初始化，假定节点编号是 1~n
for (int i = 1; i <= n; i ++ ) {
	ps[i] = i;
}

// 合并 a 和 b 所在的两个集合
ps[find(a)] = find(b);

Ⅱ、奶酪

528. 奶酪 - AcWing题库

奶酪

import java.util.*;

public class Main {
	static final int N = 1010;
	static int n, h, r;
	static Point[] points = new Point[N];
	static int[] ps = new int[N];

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		while (T-- > 0) {
			n = sc.nextInt();
			h = sc.nextInt();
			r = sc.nextInt();
			for (int i = 1; i <= n; i++)
				points[i] = new Point(sc.nextInt(), sc.nextInt(), sc.nextInt());

			// 初始化并查集
			for (int i = 1; i <= n; i++)
				ps[i] = i;

			// 连通每一个可以连通的空洞
			for (int i = 1; i <= n; i++)
				for (int j = i + 1; j <= n; j++)
					if (check(i, j))
						ps[find(j)] = find(i);

			// 存储上下面与哪些连通块连通
			HashSet<Integer> down = new HashSet<>(), up = new HashSet<>();
			for (int i = 1; i <= n; i++) {
				if (check(i, 0))
					down.add(find(i));
				if (check(i, n + 1))
					up.add(find(i));
			}

			// 校验上下底面是否可以属于同一个连通块
			boolean success = false;
			for (Integer x : down)
				if (up.contains(x)) {
					success = true;
					System.out.println("Yes");
					break;
				}
			if (!success)
				System.out.println("No");
		}
		sc.close();
	}

	// 查找x的祖宗节点
	public static int find(int x) {
		if (ps[x] != x)
			ps[x] = find(ps[x]);
		return ps[x];
	}

	// 判断两个球体是否相交或相切
	public static boolean check(int i, int j) {
		Point p1 = points[i];
		Point p2 = points[j];
		
		// 球与下底面相交相切
		if (j == 0)
			return p1.z <= r;
		// 球与上底面相交相切
		else if (j == n + 1)
			return p1.z + r >= h;
		
		// 计算两球体的距离是否大于两倍半径
		int x1 = p1.x, y1 = p1.y, z1 = p1.z;
		int x2 = p2.x, y2 = p2.y, z2 = p2.z;
		long dist = (long) (x1 - x2) * (x1 - x2) + (long) (y1 - y2) * (y1 - y2) + (long) (z1 - z2) * (z1 - z2);
		return dist <= 4 * (long) r * r;
	}

	static class Point {
		int x, y, z;

		public Point(int x, int y, int z) {
			this.x = x;
			this.y = y;
			this.z = z;
		}
	}
}

三、Flood Fill

Flood Fill 算法，即洪水填充算法或洪泛法，是用于解决连通块问题的经典算法模型；其通常可以使用 DFS 、BFS 、并查集的算法思路来实现。

复习参考：带你学习Flood Fill算法与最短路模型。

Ⅰ、实现方式

① 通过 DFS 算法递归搜索四周符合连通要求的点返回集合；

static final int N = 1010;
static char[][] matrix = new char[N][N];
static int[][] st = new int[N][N];

// 递归搜索所有与(a, b)连通的点
static void dfs(int a, int b, List<Pair> list) {
	// 添加到当前连通块集合
	list.add(new Pair(a,b));
	// 标记为已访问
	st[a][b] = 1;

	// 遍历当前位置的八个方向
	for (int x = a - 1; x < a + 1; x++) {
		for (int y = b - 1; y < b + 1; y++) {
			if (x >= 0 && y >= 0 && x < n && y < m && st[x][y] != 0 && matrix[x][y] == 'X') {
				dfs(x, y, list);
			}
		}
	}
}

② 通过 BFS 算法遍历矩阵数据查找连通块；

static final int N = 1010;
static char[][] matrix = new char[N][N];
static int[][] st = new int[N][N];
static Deque<Pair> q = new ArrayDeque<>();

// 找出点(a, b)所构成的连通块
static void bfs(int a, int b)
{
	// 首个元素入队
    q.push(new Pair(a, b));
	st[a][b] = 1;

    while(!q.isEmpty()) {
        Pair p = q.pollFirst();
        // 扩展队头（遍历所有邻接点）
		for (int x = p.x - 1; x < p.x + 1; x++) {
			for (int y = p.y - 1; y < p.y + 1; y++) {
				// 边界与连通条件判断
				if (x >= 0 	&& y >= 0 && x < n && y < m && st[x][y] != 1 && matrix[x][y] == 'X') {
					//邻接节点入队
					q.push(new Pair(x, y));
					st[x][y] = 1;
				}
			}
        }
    }
}

③ 通过并查集算法合并四周的连通部分——图中连通块的个数：并查集。

static final int N = 1010;
static char[][] matrix = new char[N][N];
static int[] ps = new int[N * N]; // 并查集辅助数组

// 将连通着的点通过并查集合并，求出连通块的个数
static int getNums() {
	int row = matrix.length;
	int col = matrix[0].length;

	// 对并查集辅助数组 ps 进行初始化
	for(int i = 0; i < row; i++)
		for(int j = 0; j < col; j++) {
			int num = col * i + j;
			ps[num] = num;
		}

	// 遍历图中的每个点
	for(int i = 0; i < row; i++)
		for(int j = 0;j < col; j++) {
			if(matrix[i][j] == 'X') {
				int down = i + 1, right = j + 1;
				if(down < row && grid[down][j] == 'X')
					ps[find(col * i + j)] = find(col * down + j); // 合并两个元素所在的集合
				if(right < col && grid[i][right] == 'X')
					ps[find(col * i + j)] = find(col * i + right);
			}
		}

	// 遍历并查集数组，统计连通块的个数
	int res = 0;
	for(int i = 0; i < row; i++)
		for(int j = 0; j < col; j++) {
			int num = col * i+j;
			if(ps[num] == num && matrix[i][j]=='X')
				res++;
		}
	return res;
}

// 并查集元素查找祖宗节点
static int find(int x) {
	if(ps[x] != x)
		ps[x] = find(ps[x]);
	return ps[x];
}

Ⅱ、动态网格

643. 动态网格 - AcWing题库

动态网格

import java.util.Scanner;

public class Main {
	static int T, R, C, N, res;
	static int[][] matrix;
	static int[] dx = {0, 1, 0, -1}, dy = {-1, 0, 1, 0};
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		T = sc.nextInt();
		for (int cases = 1; cases <= T; cases++) {
			R = sc.nextInt();
			C = sc.nextInt();
			matrix = new int[R][C];
			for (int i = 0; i < R; i++) {
				String next = sc.next();
				for (int j = 0; j < C; j++) {
					matrix[i][j] = next.charAt(j) - '0';
				}
			}
			
			N = sc.nextInt();
			sc.nextLine(); // 读取多余换行符
			System.out.println(String.format("Case #%d:", cases));
			for (int o = 0; o < N; o++) {
				String[] split = sc.nextLine().split(" ");
				if (split[0].equals("M")) { // 修改矩阵的值
					matrix[Integer.parseInt(split[1])][Integer.parseInt(split[2])] = Integer.parseInt(split[3]);
				} else { // 计算当前矩阵的连通块数量
					res = 0;
					int[][] clone = new int[R][C];
					for (int i = 0; i < matrix.length; i++) {
						clone[i] = matrix[i].clone();
					}
					for (int i = 0; i < R; i++) {
						for (int j = 0; j < C; j++) {
							if (clone[i][j] == 1) {
								dfs(clone, i ,j);
								res++;
							}
						}
					}
					System.out.println(res);
				}
			}
		}
		sc.close();
	}
	
	// DFS搜索所有连通块
	static boolean dfs(int[][] m, int a, int b) {
		int temp = m[a][b];
		m[a][b] = -1;
		if (temp == -1)
			return false;
		
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				int x = a + dx[i], y = b + dy[i];
				if (x >= 0 && x < R && y >= 0 && y < C && m[x][y] == 1) {
					dfs(m, x, y);
				}
			}
		}
		return false;
	}
}

四、哈希

Ⅰ、代码模板

// 开放寻址法
int[] h = new int[N];

// 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置
static int find(int x) {
	int t = (x % N + N) % N;
	while (h[t] != null && h[t] != x) {
		t ++ ;
		if (t == N) t = 0;
	}
	return t;
}

Ⅱ、星空之夜

1402. 星空之夜 - AcWing题库

星空之夜

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;

class Main {
	static int n, m, top, idx = 0;
	static int[][] pos;
	static char[][] matrixs;
	static double[] hash = new double[26];
	static final double eps = 1e-8;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(System.out);
		n = Integer.parseInt(br.readLine());
		m = Integer.parseInt(br.readLine());
		pos = new int[n * m][2];
		matrixs = new char[m][n];
		for (int i = 0; i < m; i++)
			matrixs[i] = br.readLine().toCharArray();
		br.close();

		for (int i = 0; i < m; i++)
			for (int j = 0; j < n; j++)
				if (matrixs[i][j] == '1') {
					top = 0;
					dfs(i, j);
					char c = getId(getHash());
					for (int k = 0; k < top; k++)
						matrixs[pos[k][0]][pos[k][1]] = c;
				}

		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++)
				pw.print(matrixs[i][j]);
			pw.println();
		}
		pw.close();
	}

	// DFS搜索每个独立星群
	public static void dfs(int a, int b) {
		matrixs[a][b] = '0';
		pos[top++] = new int[] { a, b };

		for (int x = a - 1; x <= a + 1; x++) {
			for (int y = b - 1; y <= b + 1; y++) {
				if (x >= 0 && x < m && y >= 0 && y < n && matrixs[x][y] == '1')
					dfs(x, y);
			}
		}
	}

	// 获取对应星云的ID字母
	public static char getId(double key) {
		char c = 'a';
		for (int i = 0; i < idx; i++) {
			if (Math.abs(hash[i] - key) < eps) {
				c += i;
				return c;
			}
		}
		c += idx;
		hash[idx++] = key;
		return c;
	}

	// 计算每种形状星群的Hash值
	public static double getHash() {
		double sum = 0;
		for (int i = 0; i < top; i++)
			for (int j = i + 1; j < top; j++)
				sum += getDist(pos[i], pos[j]);
		return sum;
	}

	// 两点的切比雪夫距离
	public static double getDist(int[] a, int[] b) {
		int x = a[0] - b[0];
		int y = a[1] - b[1];
		return Math.sqrt(x * x + y * y);
	}
}

五、单调栈、单调队列

算法思想复习参考：单调队列和单调栈（通俗易懂）

Ⅰ、代码模板

单调栈 —— 常见模型：找出每个数左边离它最近的比它大/小的数

static int tt = 0;

for (int i = 1; i <= n; i ++ ) {
    while (tt && check(stk[tt], i))
        tt--;
    stk[++tt] = i;
}

单调队列 —— 常见模型：找出滑动窗口中的最大值/最小值

static int hh = 0, tt = -1;

for (int i = 0; i < n; i ++ ) {
    while (hh <= tt && check_out(q[hh])) // 判断队头是否滑出窗口
        hh++;
    while (hh <= tt && check(q[tt], i))
        tt--;
    q[++tt] = i;
}

Ⅱ、矩形牛棚

1413. 矩形牛棚 - AcWing题库

矩形牛棚

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class Main {
	static final int N = 3010;
	static int r, c, p, res = 0;
	static int[][] broken = new int[N][N];
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] split = br.readLine().split(" ");
		r = Integer.parseInt(split[0]);
		c = Integer.parseInt(split[1]);
		p = Integer.parseInt(split[2]);
		for (int i = 0; i < p; i++) {
			split = br.readLine().split(" ");
			broken[Integer.parseInt(split[0])][Integer.parseInt(split[1])] = -1;
		}
		
		// 枚举下边界
		for (int i = 1; i <= r; i++) {
			// 递推计算下边界高度
			for (int j = 1; j <= c; j++) {
				if (broken[i][j] == -1)
					broken[i][j] = 0;
				else
					broken[i][j] = 1 + broken[i - 1][j];
			}
			// 通过单调栈找出小于当前元素的最近元素
			int[] left = new int[c + 5], right = new int[c + 5];
			Arrays.fill(right, c + 1);
			Deque<Integer> stack = new ArrayDeque<Integer>();
			for (int j = c; j > 0; j--) {
				while (!stack.isEmpty() && broken[i][j] < broken[i][stack.peek()])
					left[stack.pop()] = j;
				stack.push(j);
			}
			stack.clear();
			for (int j = 1; j <= c; j++) {
				while (!stack.isEmpty() && broken[i][j] < broken[i][stack.peek()])
					right[stack.pop()] = j;
				stack.push(j);
			}
			// 枚举计算最大矩阵面积
			for (int j = 1; j <= c; j++) {
				res = Math.max(res, broken[i][j] * (right[j] - left[j] - 1));
			}
		}
		System.out.println(res);
	}
}

标签：Week,BFS,ps,int,蓝桥,++,static,&&,new
From： https://www.cnblogs.com/tfiyuenlau/p/18095192

相关文章

  • 蓝桥杯练习题——博弈论
    1.必胜态后继至少存在一个必败态2.必败态后继均为必胜态Nim游戏思路23，先手必赢，先拿1，然后变成22，不管后手怎么拿，先手同样操作，后手一定先遇到00a1^a2^a3…^an=0，先手必败，否则先手必胜#include<iostream>usingnamespacestd;constintN=1e5+1......
  • P8687 [蓝桥杯 2019 省 A] 糖果
    题意：n个零食，每个零食有k种配料，一共有m种配料。问最少吃几包零食，可以吃到所有配料。n<=100,m<=20,k<=m。思路：最优化问题，如果n<=20可以直接bf，这里m<=20，对m进行状态压缩，正确的解法应该是线性dp+状态压缩。总结：很容易陷入一个哈密顿路径思路的误区中，在哈密顿路径中，一......
  • 数学算法（算法竞赛、蓝桥杯）--判定质数试除法
    1、B站视频链接：G06判定质数试除法_哔哩哔哩_bilibili题目链接：【深基7.例2】质数筛-洛谷#include<bits/stdc++.h>usingnamespacestd;boolis_prime(intx){ if(x==1)return0;//特判1不是质数 for(inti=2;i*i<=x;i++){//枚举小的那个到根号n即可 if(x%i==0......
  • 2024 Mar. Week-3 Summary
    2024Mar.Week-3Summary2024.03.18-2024.03.24感觉超级久没写总结...虽然但是题解之类的一直在写补题上周主要做数据结构，把lxl的题单补到\(Day~4\)乐主要板块：树套树，分块但是效率还是有点低，一道题要做\(INF\)分钟，可能还是不够熟练自己切题的能力比较差，很多......
  • Weekly Contest 390
    ProblemA每个字符最多出现两次的最长子字符串思路双指针，使用一个数组记录每个字符的出现次数，当出现次数大于2时l往左收缩其余情况往右划代码classSolution{publicintmaximumLengthSubstring(Strings){intn=s.length();int[]cnt=newint......
  • P8716 [蓝桥杯 2020 省 AB2] 回文日期
    思路解析本题与洛谷的P2010[NOI......
  • 2024 蓝桥打卡Day18
    洛谷刷题P8682[蓝桥杯2019省B]等差数列题目[P8682[蓝桥杯2019省B]等差数列](https://www.luogu.com.cn/problem/P8682)题解P8682[蓝桥杯2019省B]等差数列题目P8682[蓝桥杯2019省B]等差数列题解importjava.util.Arrays;importjava.util.S......
  • 浅析BFS
    广度优先搜索(BFS)广度优先算法（BFS）又称宽度优先搜索，是指依次将与根节点路径长度（默认每条边长度相同）相同的点遍历，再遍历路径长度加一的点，直到遍历完整个图结束。BFS在树中的应用作用：BFS用于在树中搜索某个特定的数据。方法：从根节点开始搜索，按层遍历整个树。一般使用队......
  • 第十二届蓝桥杯省赛C&C++ 研究生组
    十二届省赛题第十二届蓝桥杯省赛C&C++研究生组-卡片第十二届蓝桥杯省赛C&C++研究生组-直线第十二届蓝桥杯省赛C&C++研究生组-货物摆放第十二届蓝桥杯省赛C&C++研究生组-路径第十二届蓝桥杯省赛C&C++研究生组-时间显示第十二届蓝桥杯省赛C&C++研究生组-砝码称重......
  • [暴力题解系列]2023年蓝桥杯-整数删除（30分）
    这题暴力最多30分，但是30分也是分，做暴力的人不能贪心，拿到分就是赚了。​ 这题核心烦人点在于他数据分层断崖，就只有前3个点能做到稳过。用的思路就是链表，但不是用指针存的，而是用数组下标为标记存的，只是我觉得因为这样好写一些。链表方便修改左右连接位置，所以越到后面就越能省下查询......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99