小美的字符串变换

[编程题]小美的字符串变换

热度指数：1271 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

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

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

输入描述:

第一行输入一个正整数，代表字符串的长度。
第二行输入一个长度为的、仅由小写字母组成的字符串。

输出描述:

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

示例1

输入

9
aababbabb

输出

说明

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

算法知识视频讲解

Python

开心的修勾在划水

nn = int(input())
s = list(input())

# 行列可能的情况
mn=[]
for i in range(1,nn):
    if nn%i==0:
        mn.append((i,nn//i))
#回溯
def dfs(row,col,m,n,c):
    ##用行列来计算在一维数组中的角标
    i = row*n+col
    if row< 0&nbs***bsp;row>=m&nbs***bsp;col<0&nbs***bsp;col>=n&nbs***bsp;used[i]==1&nbs***bsp;s[i]!=c:
        return
    used[i] = 1
    dfs(row+1,col,m,n,c)
    dfs(row-1,col,m,n,c)
    dfs(row,col+1,m,n,c)
    dfs(row,col-1,m,n,c)

#计算
min_res=float('inf')
for m,n in mn:
    used = [0 for _ in range(nn)]
    res=0
    for i in range(m):
        for j in range(n):
            idx = i*n+j
            if used[idx]==0:
                ##如果某个元素未被检索到，则这次会检索到并且res+=1
                res+=1
                dfs(i,j,m,n,s[idx])
    min_res=min(min_res,res)
print(min_res)

编辑于 2023-08-17 15:44:34 回复(0)