uq_43625241302

用户名：uq_43625241302

访问量：2890

签　名：

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

　　自我简介：

TA的其他文章

贪心 + 优先队列
浏览：806

模拟分类（标题不能太短）
浏览：378

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

你可能喜欢

并查集 + 模拟 = 恶心

　　作者: uq_43625241302　　　　发表时间：2023-04-29 18:28:28 浏览：514　|　评论：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 人评分

C语言网推出会员服务，提供C/C++/算法/Python等多套视频学练课程+源码资源社群答疑+私活推荐等资源，享受丰富的技术学习到变现的乐趣，以含金量和学习效果勇敢挑战同类辅导！点击了解开通

　　评论区

怪白

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二级辅导-阶乘数列（C语言代码）

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

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

C语言训练-计算1~N之间所有奇数之和（C语言代码）

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

并查集 + 模拟 = 恶心

评论区

精彩推荐

时间转换（Java代码）

C语言训练-角谷猜想（C语言代码）

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

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

K-进制数（C语言描述，蓝桥杯）

【偶数求和】（C语言代码）

DNA （C语言代码）

printf基础练习2 （C语言代码）

1051（奇了怪了）

整除问题（C语言代码）

uq_43625241302

TA的其他文章

你可能喜欢

C二级辅导-阶乘数列 （C语言代码）

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

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

C语言训练-计算1~N之间所有奇数之和 （C语言代码）

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

并查集 + 模拟 = 恶心

评论区

精彩推荐

时间转换 （Java代码）

C语言训练-角谷猜想 （C语言代码）

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

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

K-进制数 （C语言描述，蓝桥杯）

【偶数求和】 （C语言代码）

DNA （C语言代码）

printf基础练习2 （C语言代码）

1051（奇了怪了）

整除问题 （C语言代码）

C二级辅导-阶乘数列（C语言代码）

C语言训练-计算1~N之间所有奇数之和（C语言代码）

　　评论区

时间转换（Java代码）

C语言训练-角谷猜想（C语言代码）

K-进制数（C语言描述，蓝桥杯）

【偶数求和】（C语言代码）

整除问题（C语言代码）