uq_43625241302

用户名：uq_43625241302

访问量：3160

签　名：

等　　级
排　　名	7726
经　　验	1287
参赛次数	1
文章发表	6
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

预处理 + 双端队列
浏览：365

你可能喜欢

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）scanf后面加个getchar（），收掉回车符，就可以用gets了

并查集 + 模拟 = 恶心

　　作者: uq_43625241302　　　　发表时间：2023-04-29 18:28:28 浏览：557　|　评论：1　

原题链接：蓝桥杯2023年第十四届省赛真题-合并区域

# 并查集 + 模拟
总结：真的很恶心
## 解题思路
该有的注释都有了

## 代码实现
```java

import java.util.*;
public class Main {
    public static void main(String[] args) {
        new Main().go();
    }

static class UnionFind {
        int[] parent;
        public UnionFind(int capacity) {
            parent = new int[capacity];
            for(int i = 0; i < capacity; i++) {
                parent[i] = i;
            }
        }

public int find(int x) {
            if(parent[x] == x) return x;
            int fa = find(parent[x]);
            parent[x] = fa;
            return fa;
        }

public void union(int x1, int x2) {
            int root1 = find(x1), root2 = find(x2);
            if(root1 == root2) return;
            parent[root1] = root2;
        }
    }

private final Scanner sc = new Scanner(System.in);
    private int[][] m1;
    private int[][] m2;

public void go() {
        int n = sc.nextInt();
        m1 = getMatrix(n);
        m2 = getMatrix(n);

System.out.println(getRes());
    }

public int[][] getMatrix(int n) {
        int[][] matrix = new int[n][n];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                matrix[i][j] = sc.nextInt();
            }
        }
        return matrix;
    }

private UnionFind uf1;
    private UnionFind uf2;
    
    private int n;
    private Map<Integer, Integer> map1;
    private Map<Integer, Integer> map2;
    public int getRes() {
        uf1 = getUnionFind(m1);
        uf2 = getUnionFind(m2);

n = m1.length;
        map1 = new HashMap<>();
        map2 = new HashMap<>();
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(m1[i][j] == 1) {
                    int key1 = uf1.find(i * n + j);
                    map1.put(key1, map1.getOrDefault(key1, 0) + 1);
                }

if(m2[i][j] == 1) {
                    int key2 = uf2.find(i * n + j);
                    map2.put(key2, map2.getOrDefault(key2, 0) + 1);
                }
            }
        }

int sum = 0;
        // 第一种情况：答案有可能在单独一个矩阵的内部
        for(int key : map1.keySet()) sum = Math.max(sum, map1.get(key));
        for(int key : map2.keySet()) sum = Math.max(sum, map2.get(key));

// 第二种情况：答案由两个矩阵合并得到
        // 此时，我们固定一个矩阵不动，旋转第二个矩阵，将第二个矩阵的每条边与第一个矩阵的每条边匹配
        for(int i = 0; i < 4; i++) {
            for(int j = 0; j < 4; j++) {
                sum = Math.max(sum, getUnionMaxSum(i, j));
            }
        }
        
        return sum;
    }

// 所有方向是从上到下，从左到右，因此
    // 第一行 --> 第一列：不需要逆序
    // 第一列 --> 最后一行  需要逆序
    // 最后一行 --> 第一列  不需要逆序
    // 第一列 --> 第一行 需要逆序
    private static final int[] needReverse = new int[]{0, 1, 0, 1};

/**
     * 思路：将一个矩阵中的每一个连通块去对应另外一个矩阵所有能对应的连通块，最后加起来就是答案
     * @param x1 表示对应矩阵1的哪条边
     * @param x2 表示对应矩阵2的哪条边
     */
    public int getUnionMaxSum(int x1, int x2) {
        int ans = 0;
        // 考虑顺时针旋转可能会造成的翻转
        int target = (x1 + 2) % 4;
        int flag = 0;
        int temp = x2;
        while (temp != target) {
            flag += needReverse[temp];
            temp = (temp + 1) % 4;
        }
        for(int i = - n + 1; i < n; i++) {    // i表示第二个矩阵对应的第一个矩阵的偏移量
            Map<Integer, Set<Integer>> mapSet1 = new HashMap<>();
            // 记录 map1 中每个元素与之对应的 map2中的每个元素的和
            Map<Integer, Set<Integer>> mapSet2 = new HashMap<>();
            for(int j = 0; j < n; j++) {
                int x = (flag == 1) ? (n - 1 - i - j) : (i + j);
                if(x < 0 || x >= n) continue;

int idx1 = getKey(j, x1);
                int idx2 = getKey(x, x2);
                if(m1[idx1 / n][idx1 % n] == 0 || m2[idx2 / n][idx2 % n] == 0) continue;

// 每个 Map中存放对面的并查集中的元素
                int key1 = uf1.find(idx1);
                int key2 = uf2.find(idx2);
                mapSet1.putIfAbsent(key1, new HashSet<>());
                Set<Integer> set1 = mapSet1.get(key1);
                set1.add(key2);

mapSet2.putIfAbsent(key2, new HashSet<>());
                Set<Integer> set2 = mapSet2.get(key2);
                set2.add(key1);
            }
            int max = 0;
            for(int key : mapSet1.keySet()) {
                set1 = new HashSet<>();
                set2 = new HashSet<>();

dfs(mapSet1, mapSet2, key, true);
                int sum = 0;
                for(int setKey : set1) sum += map1.get(setKey);
                for(int setKey : set2) sum += map2.get(setKey);
                max = Math.max(sum, max);
            }
            ans = Math.max(ans, max);
        }
        return ans;
    }

private Set<Integer> set1;
    private Set<Integer> set2;

/**
     * 获取当前连通块所有连通块的编号
     * @param mapSet1
     * @param mapSet2
     * @param key
     * @param flag
     */
    public void dfs(Map<Integer, Set<Integer>> mapSet1, Map<Integer, Set<Integer>> mapSet2, int key, boolean flag) {
        if(flag) {
            set1.add(key);
            for(int k : mapSet1.get(key)) {
                if(!set2.contains(k)) dfs(mapSet1, mapSet2, k, false);
            }
        }else {
            set2.add(key);
            for(int k : mapSet2.get(key)) {
                if(!set1.contains(k)) dfs(mapSet1, mapSet2, k, true);
            }
        }
    }

/**
     * 获取边界的id：元素顺序为从上到下，从左到右
     * @param x 当前为第几个元素
     * @param idx 选择四个边界中的哪一个
     * @return 元素的编号id
     */
    private int getKey(int x, int idx) {
        // 第一行
        if(idx == 0) return x;
        // 最后一列
        else if(idx == 1) return x * n + n - 1;
        // 最后一行
        else if(idx == 2) return n * (n - 1) + x;
        // 第一列
        else return x * n;
    }

// 向量：定位上下左右
    private static final int[] dx = new int[]{0, 0, 1, -1};
    private static final int[] dy = new int[]{1, -1, 0, 0};

/**
     * 将所有的1合并，成为一个连通块
     * @param matrix 当前矩阵
     * @return 合并后的并查集
     */
    public UnionFind getUnionFind(int[][] matrix) {
        int n = matrix.length;
        UnionFind uf = new UnionFind(n * n + 1);
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(matrix[i][j] == 1) {
                    // 如果为1，则将其上下左右合并到当前元素的连通块中
                    for(int k = 0; k < 4; k++) {
                        int x = i + dx[k], y = j + dy[k];
                        if(x >= 0 && x < n && y >= 0 && y < n && matrix[x][y] == 1) {
                            uf.union(x * n + y, i * n + j);
                        }
                    }
                }
            }
        }

return uf;
    }
}

```

0.0分

3 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

怪白

11
0 1 1 0 1 1 0 1 1 0 1 
1 0 0 1 1 0 0 1 0 0 1 
0 0 0 1 0 1 1 1 1 1 1 
1 0 1 0 0 0 1 0 1 1 0 
0 0 0 0 0 0 0 0 0 0 1 
1 0 0 1 1 1 0 0 1 1 1 
1 0 1 0 1 1 0 0 0 1 0 
0 1 1 0 0 1 1 0 1 1 0 
1 1 1 0 0 0 0 1 1 0 0 
0 0 0 0 0 1 0 1 0 1 1 
0 1 1 0 0 0 0 1 1 0 1 
0 0 0 0 1 0 0 0 1 1 0 
1 1 0 0 1 0 1 1 1 0 1 
0 0 0 0 0 0 0 0 1 0 1 
1 1 1 0 0 1 1 1 1 1 0 
0 0 1 0 0 0 0 1 0 1 1 
1 0 1 0 0 0 1 1 0 1 0 
1 1 1 1 0 0 1 0 0 0 1 
0 0 0 1 0 0 1 1 1 1 1 
0 0 0 0 0 1 0 0 0 0 1 
0 0 0 0 1 1 0 0 1 0 1 
1 1 1 0 0 1 0 0 1 1 0 
这组数据错了54

2023-06-08 13:25:01

uq_43625241302

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

C二级辅导-求偶数和（C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）scanf后面加个getchar（），收掉回车符，就可以用gets了

简单的a+b （C语言代码）

C语言考试练习题_一元二次方程（C语言代码）

并查集 + 模拟 = 恶心

评论区

精彩推荐

母牛的故事（C语言代码）

星期判断机（C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

C二级辅导-同因查找（C语言代码）

一元一次方程（C语言代码）

C语言程序设计教程（第三版）课后习题12.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

A+B for Input-Output Practice (I) （C++代码）

WU-玉龙学长买雪糕（C++代码）

字符串的修改（C++代码）

uq_43625241302

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

C二级辅导-求偶数和 （C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）scanf后面加个getchar（），收掉回车符，就可以用gets了

简单的a+b （C语言代码）

C语言考试练习题_一元二次方程 （C语言代码）

并查集 + 模拟 = 恶心

评论区

精彩推荐

母牛的故事 （C语言代码）

星期判断机 （C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

C二级辅导-同因查找 （C语言代码）

一元一次方程 （C语言代码）

C语言程序设计教程（第三版）课后习题12.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

A+B for Input-Output Practice (I) （C++代码）

WU-玉龙学长买雪糕 （C++代码）

字符串的修改 （C++代码）

C二级辅导-求偶数和（C语言代码）

C语言考试练习题_一元二次方程（C语言代码）

　　评论区

母牛的故事（C语言代码）

星期判断机（C语言代码）

C二级辅导-同因查找（C语言代码）

一元一次方程（C语言代码）

WU-玉龙学长买雪糕（C++代码）

字符串的修改（C++代码）