小美的字符串变换

DFS连通图

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        String string =in.next();
        if(n==1){
            System.out.print(1);
            return;
        }
        
        int res=10000;
        for(int x=1;x<=n/2;x++){
            if(n%x==0){
                int count=0;
                int y=n/x;
                char[][] m=new char[x][y];
                for(int i=0;i<x;i++){
                    for(int j=0;j<y;j++){
                        m[i][j]=string.charAt(i*y+j);
                    }
                }
                boolean[][] visited=new boolean[x][y];
                for(int i=0;i<x;i++){
                    for(int j=0;j<y;j++){
                        if(!visited[i][j]){
                            char s=m[i][j];
                            dfs(m,i,j,visited,s);
                            count++;
                        }
                    }
                }
                res=Math.min(res,count);
            }
        }
        System.out.print(res);
    }
    public static void dfs(char[][] m,int r,int c,boolean[][] visited,char s){
        //char s=m[r][c];
        if(!isin(m,r,c) || m[r][c]!=s || visited[r][c]){
            return ;
        }

        visited[r][c]=true;

        dfs(m,r-1,c,visited,s);
        dfs(m,r+1,c,visited,s);
        dfs(m,r,c-1,visited,s);
        dfs(m,r,c+1,visited,s);
    }

    public static boolean isin(char[][] m,int r,int c){
        return (r>=0 && r<m.length && c>=0 && c<m[0].length);
    }
}

此题是经典的并查集模板题。首先生成行列乘积为n的二阶矩阵，再根据矩阵中元素上下左右值是否与之相等选择是否union，最后得到并查集中集合数量。取所有二阶矩阵并查集中集合数量最小值即为解。

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        char[] str = sc.next().toCharArray();
        int q = n;
        for (int i = 1; i <= n; i++) {
            if (n % i == 0) {
                int N = i;
                int M = n / i;
                int[][] board = new int[N][M];
                int index = 0;
                for (int j = 0; j < N; j++) {
                    for (int k = 0; k < M; k++) {
                        board[j][k] = str[index++];
                    }
                }
                q = Math.min(q, q(board));
            }
        }
        System.out.println(q);
    }

    public static int q(int[][] board) {
        int N = board.length;
        int M = board[0].length;
        UnionFind uf = new UnionFind(N * M);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                int cur = i * M + j;
                if (i - 1 >= 0 && board[i - 1][j] == board[i][j]) {
                    uf.union(cur - M, cur);
                }
                if (i + 1 < N && board[i + 1][j] == board[i][j]) {
                    uf.union(cur + M, cur);
                }
                if (j - 1 >= 0 && board[i][j - 1] == board[i][j]) {
                    uf.union(cur - 1, cur);
                }
                if (j + 1 < M && board[i][j + 1] == board[i][j]) {
                    uf.union(cur + 1, cur);
                }
            }
        }
        return uf.size();
    }

    public static class UnionFind {
        private int[] parent;
        private int[] sizeMap;
        private int size;

        public UnionFind(int N) {
            size = N;
            parent = new int[N];
            sizeMap = new int[N];
            for (int i = 0; i < N; i++) {
                parent[i] = i;
                sizeMap[i] = 1;
            }
        }

        public int size() {
            return size;
        }

        private int find(int v) {
            if (v != parent[v]) {
                parent[v] = find(parent[v]);
            }
            return parent[v];
        }

        public void union(int v1, int v2) {
            int f1 = find(v1);
            int f2 = find(v2);
            if (f1 != f2) {
                size--;
                int s1 = sizeMap[f1];
                int s2 = sizeMap[f2];
                if (s1 > s2) {
                    parent[f2] = f1;
                    sizeMap[f1] += s2;
                } else {
                    parent[f1] = f2;
                    sizeMap[f2] += s1;
                }
            }
        }
    }
}