小美的字符串变换

https://mp.weixin.qq.com/s/NVSAjmmL48_PtLIOKXVQqg

题目

题目描述

小美拿到了一个长度为n的字符串，她希望将字符串从左到右平铺成一个矩阵（先平铺第一行，然后是第二行，以此类推，矩阵有x行y列，必须保证$x\ast y=n$，即每y个字符换行，共x行）。

该矩阵的权值定义为这个矩阵的连通块数量。小美希望最终矩阵的权值尽可能小，你能帮小美求出这个最小权值吗？

注：我们定义，上下左右四个方向相邻的相同字符是连通的。

输入描述

第一行输入一个正整数n，代表字符串的长度。

第二行输入一个长度为n的、仅由小写字母组成的字符串。

$1<=n<={10}^4$

输出描述

输出一个整数表示最小权值。

示例1

输入

9 
aababbabb

输出

2 

说明

平铺为3*3的矩阵：
aab
abb
abb
共有2个连通块，4个a和5个b。 

思路与代码

枚举可能分割的行列，并查集检查连通性。

import java.util.Collections;  
import java.util.LinkedList;  
import java.util.List;  
import java.util.Scanner;  
  
  
public class Main {  
  
    static List<Integer> get_divisors(int n) {  
        List<Integer> res = new LinkedList<>();  
        for (int i = 1 ; i <= n /i ; i++) {  
            if (n%i == 0) {  
                res.add(i);  
                if (i!=n/i) res.add(n/i);  
            }  
        }  
        Collections.sort(res);  
        return res;  
    }  
  
    static int[] fa;  
  
    static void init(int n) {  
        fa = new int[n];  
        for (int i = 0; i < n; i++) fa[i] = i;  
    }  
    //找到x的根节点  
    static int find(int x) {  
        return x == fa[x] ? x : (fa[x] = find(fa[x]));  
    }  
    //合并两个节点  
    static void union(int x, int y) {  
        fa[find(x)] = find(y);  
    }  
  
    static int getConn(int x, int y, char[] cs) {  
        init(x*y+1);  
        int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};  
        for (int i = 0; i < x; i++) {  
            for (int j = 0; j < y; j++) {  
                for (int[] dir : dirs) {  
                    int ni = i + dir[0], nj = j + dir[1];  
                    if (ni < 0 || nj < 0 || ni >= x || nj >= y || cs[i*y+j] != cs[ni*y + nj])continue;  
                    union(i*y+j, ni*y+nj);  
                }  
            }  
        }  
  
        int res = 0;  
        for (int i = 0; i < x; i++) {  
            for (int j = 0; j < y; j++) {  
                if (find(i*y+j) == i*y+j)res++;  
            }  
        }  
        return res;  
    }  
  
    public static void main(String[] args) {  
        Scanner sc = new Scanner(System.in);  
        int n = Integer.parseInt(sc.nextLine());  
        String s = sc.nextLine();  
        List<Integer> divs = get_divisors(n);  
        int res = Integer.MAX_VALUE;  
        for (int div : divs) {  
            if (div != n)res = Math.min(res, getConn(div, n/div,s.toCharArray()));  
        }  
        System.out.println(res);  
    }  
}