💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 大厂实习经历

👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸

✨ 合集传送们 -> 🧷学长刷题笔记

🍒 本专栏已收集 140+ 套题 🍄 题面描述等均已改编，如果和你实际看到的题面描述不一样请理解，做法和题目本质基本不变。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力 💞

🍥 本次题目难度不是很大，感觉第一题和第二题的难度反了

1️⃣ 看到连通块数量，一般就三种写法， DFS/BFS/并查集

2️⃣ 模拟题，难度个人认为不如第一题

🦩 01.彩色魔法森林

问题描述

LYA是一位魔法师，她在一片无边无际的魔法森林中施展魔法。这片森林由无数个正方形区域组成，初始时所有区域都是白色的。LYA有两种魔法：

1. 红色魔法：将一个区域及其上下左右四个相邻区域变成红色。
2. 黑色魔法：将一个区域及其上下左右四个相邻区域变成黑色。

LYA想知道在施展了一系列魔法后，森林中红色和黑色的连通区域各有多少个。两个同色相邻的区域属于同一个连通区域。

输入格式

第一行输入一个整数 ，表示LYA施展魔法的次数。

接下来 行，每行输入三个整数 、 和 。

• 和 表示施法的中心区域坐标。
• 表示魔法类型， 为红色魔法， 为黑色魔法。

输出格式

输出一行两个整数，分别表示红色连通区域的数量和黑色连通区域的数量。

样例输入

4
2 3 0
3 2 1
3 3 0
2 4 1

样例输出

2 3

样例解释

在施展完所有魔法后，森林中形成了2个红色连通区域和3个黑色连通区域。

数据范围

题解

本题的核心思路是使用并查集来处理连通区域。

当然最后处理的时候用BFS/DFS代替并查集也是ok的

我们需要注意以下几点：

1. 由于坐标范围很大，我们需要使用哈希表来存储实际被染色的区域。
2. 对于每次施法，我们需要处理中心区域及其相邻的四个区域。
3. 使用并查集合并相同颜色的相邻区域。
4. 最后统计不同颜色的连通区域数量。

参考代码

• Python

# 定义并查集类
class DSU:
    def __init__(self):
        self.parent = {}
        self.size = {}
    
    # 查找元素所属集合的根
    def find(self, x):
        if x not in self.parent:
            self.parent[x] = x
            self.size[x] = 1
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    # 合并两个集合
    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx != ry:
            if self.size[rx] < self.size[ry]:
                rx, ry = ry, rx
            self.parent[ry] = rx
            self.size[rx] += self.size[ry]

# 主函数
def solve():
    n = int(input())
    grid = {}
    dsu = DSU()
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    
    # 处理每次施法
    for _ in range(n):
        x, y, c = map(int, input().split())
        c += 1  # 将颜色转换为1（红）或2（黑）
        grid[(x, y)] = c
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            grid[(nx, ny)] = c
    
    # 合并相同颜色的相邻区域
    for (x, y), color in grid.items():
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if (nx, ny) in grid and grid[(nx, ny)] == color:
                dsu.union((x, y), (nx, ny))
    
    # 统计连通区域数量
    roots = set()
    for pos in grid:
        roots.add(dsu.find(pos))
    
    red = sum(1 for pos in roots if grid[pos] == 1)
    black = sum(1 for pos in roots if grid[pos] == 2)
    
    print(red, black)

solve()

• Java

import java.util.*;
import java.io.*;

public class Main {
    // 并查集类
    static class DSU {
        Map<Long, Long> parent = new HashMap<>();
        Map<Long, Integer> size = new HashMap<>();
        
        // 查找元素所属集合的根
        long find(long x) {
            if (!parent.containsKey(x)) {
                parent.put(x, x);
                size.put(x, 1);
            }
            if (parent.get(x) != x) {
                parent.put(x, find(parent.get(x)));
            }
            return parent.get(x);
        }
        
        // 合并两个集合
        void union(long x, long y) {
            long rx = find(x), ry = find(y);
            if (rx != ry) {
                // 将小的集合合并到大的集合中
                if (size.get(rx) < size.get(ry)) {
                    long temp = rx;
                    rx = ry;
                    ry = temp;
                }
                parent.put(ry, rx);
                size.put(rx, size.get(rx) + size.get(ry));
            }
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Map<Long, Integer> grid = new HashMap<>();
        DSU dsu = new DSU();
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, 1, 0, -1};
        
        // 处理每次施法
        for (int i = 0; i < n; i++) {
            String[] input = br.readLine().split(" ");
            int x = Integer.parseInt(input[0]);
            int y = Integer.parseInt(input[1]);
            int c = Integer.parseInt(input[2]) + 1;  // 将颜色转换为1（红）或2（黑）
            long key = (long)x << 32 | y;
            grid.put(key, c);
            // 处理相邻的四个格子
            for (int j = 0; j < 4; j++) {
                long nkey = ((long)(x + dx[j]) << 32) | (y + dy[j]);
                grid.put(nkey, c);
            }
        }
        
        // 合并相同颜色的相邻区域
        for (Map.Entry<Long, Integer> entry : grid.entrySet()) {
            long key = entry.getKey();