思路：枚举+BFS

首先看这个数据范围，可以知道的是一个数的因子数不会太大。暴力枚举可以发现，10000以内因子数最大的数是 $9240$ ，共有 $64$ 个因子。

所以可以枚举因子来确定矩阵的行数和列数。即枚举$x*y=n$ 中的$x$ , 然后$y = n / x$

接着根据结果构造出新矩阵，在新矩阵上进行BFS求连通块。

这样最多跑 $64$ 次 $BFS$ 求连通块。

时间复杂度：$O(64n)$

代码

C++

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;

int len;
string s;

const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
int main()
{
    cin >> len;
    cin >> s;

    vector<int> vis(len);
    auto get = [&](int n, int m) {
        queue<PII> q;
        int res = 0;
        for (int i = 0; i < len; ++i) vis[i] = 0;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j) {
                if (vis[i * m + j]) continue;
                char ch = s[i * m + j];
                q.emplace(i, j);
                while (!q.empty()) {
                    auto top = q.front(); q.pop();
                    for (int k = 0; k < 4; ++k) {
                        int nx = top.first + dx[k], ny = top.second + dy[k];
                        if (nx >= 0 && nx < n && ny >= 0 && ny < m && !vis[nx * m + ny] && s[nx * m + ny] == ch) {
                            vis[nx * m + ny] = 1;
                            q.emplace(nx, ny);
                        }
                    }
                }
                res += 1;
            }
        return res;
    };

    int mid = len / 2;
    int ans = 0x3f3f3f3f;
    for (int i = 1; i <= mid; ++i) {
        if (len % i == 0) {
            ans = min(ans, get(i, len / i));
        }
    }
    cout << ans << "\n";
    return 0;
}

python

from collections import deque

len = int(input())
s = input()

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

def get(n, m):
    q = deque()
    res = 0
    vis = [0] * len

    for i in range(n):
        for j in range(m):
            if vis[i * m + j]:
                continue
            ch = s[i * m + j]
            q.append((i, j))
            while q:
                top = q.popleft()
                for k in range(4):
                    nx = top[0] + dx[k]
                    ny = top[1] + dy[k]
                    if nx >= 0 and nx < n and ny >= 0 and ny < m and not vis[nx * m + ny] and s[nx * m + ny] == ch:
                        vis[nx * m + ny] = 1
                        q.append((nx, ny))
            res += 1
    return res

mid = len // 2
ans = float('inf')

for i in range(1, mid + 1):
    if len % i == 0:
        ans = min(ans, get(i, len // i))

print(ans)

Java

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;

public class Main {

    static int len;
    static String s;

    static final int[] dx = {-1, 0, 1, 0};
    static final int[] dy = {0, 1, 0, -1};

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        len = scanner.nextInt();
        scanner.nextLine(); // Consume the newline character
        s = scanner.nextLine();

        int mid = len / 2;
        int ans = Integer.MAX_VALUE;

        for (int i = 1; i <= mid; ++i) {
            if (len % i == 0) {
                ans = Math.min(ans, get(i, len / i));
            }
        }

        System.out.println(ans);
    }

    static int get(int n, int m) {
        Queue<int[]> queue = new ArrayDeque<>();
        int res = 0;
        int[] vis = new int[len];

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (vis[i * m + j] != 0) {
                    continue;
                }
                char ch = s.charAt(i * m + j);
                queue.offer(new int[]{i, j});
                while (!queue.isEmpty()) {
                    int[] top = queue.poll();
                    for (int k = 0; k < 4; ++k) {
                        int nx = top[0] + dx[k];
                        int ny = top[1] + dy[k];
                        if (nx >= 0 && nx < n && ny >= 0 && ny < m && vis[nx * m + ny] == 0 && s.charAt(nx * m + ny) == ch) {
                            vis[nx * m + ny] = 1;
                            queue.offer(new int[]{nx, ny});
                        }
                    }
                }
                res += 1;
            }
        }

        return res;
    }
}

题目内容

给定一个长度为$n$的字符串。你可以把他转换成一个大小为$x*y$ 的矩形，例如:

$abc$ 可以变成 $\begin{bmatrix} a & b & c \end{bmatrix}$ 也可以变成 $\begin{bmatrix} a \\ b\\ c \end{bmatrix}$ .

你需要保证$x * y = n$ .

接着，我们定义一个矩阵的权值为这个矩阵的连通块数量。

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

请在所有可能的矩阵种找到一个权值最小的矩阵，并输出权值。

输入描述

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

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

$1 \leq n \leq 10^4$

输出描述

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

样例

输入输出示例仅供调试，后台判题数据一般不包含示例

输入

8
abaababa

输出

3

说明

转换成$4*2$ 的矩阵:

$ab$

$aa$

$ba$

$ba$

共有$3$个连通块，$1$个$a$ 和$2$个$b$。