小美拿到了一个长度为的字符串，她希望将字符串从左到右平铺成一个矩阵（先平铺第一行，然后是第二行，以此类推，矩阵有行列，必须保证，即每个字符换行，共行）。 该矩阵的权值定义为这个矩阵的连通块数量。小美希望最终矩阵的权值尽可能小，你能帮小美求出这个最小权值吗？ 注：我们定义，上下左右四个方向相邻的相同字符是连通的。
区块链毕设网qklbishe.com为您提供问题的解答
小美拿到了一个长度为
的字符串，她希望将字符串从左到右平铺成一个矩阵（先平铺第一行，然后是第二行，以此类推，矩阵有
行
列，必须保证
，即每个字符换行，共行）。
该矩阵的权值定义为这个矩阵的连通块数量。小美希望最终矩阵的权值尽可能小，你能帮小美求出这个最小权值吗？
注：我们定义，上下左右四个方向相邻的相同字符是连通的。
使用并查集求解的，为什么for( int x = 1 ; x * x <= n; ++x)通过不了第10个用例，而for(int x =1 ; x <= n; ++x)就可以了
#include <bits/stdc++.h> using namespace std; class DSU{ public: vector<int> nums; DSU(int n ){ nums.resize(n); for(int i = 0; i < n; ++i) nums[i] = i; } int findParent(int x){ int y = x; while(y != nums[y]) y = nums[y]; while(x != nums[x]){ int temp = x; x = nums[x]; nums[temp] = y; } return y; } void merge(int x, int y){ int parx = findParent(x); int pary = findParent(y); nums[parx] = pary; } int getUnion(){ int ans = 0; for(int i = 0; i < nums.size(); ++i) if(nums[i] == i) ++ans; return ans; } }; int dfs(const string& str, int m, int n){ DSU dsu(m*n); for(int i = 0; i < m; ++i) for(int j = 0; j < n; ++j){ if(i >= 1 && str[(i-1)*n+j] == str[i*n+j]) dsu.merge((i-1)*n+j, i*n+j); if(j >= 1 && str[i*n+j-1] == str[i*n+j]) dsu.merge(i*n+j-1, i*n+j); } return dsu.getUnion(); } int main(){ int n; int ans = INT_MAX; cin >> n; string str; cin >> str; for(int x = 1; x*x <= n; ++x){ if(n%x) continue; int y = n/x; ans = min(ans,dfs(str,x,y)); } cout << ans << endl; return 0; } // 64 kmnplvqksghziolcfczxpygfiahpgqdaezyjmbwvwgotojprgoqjyeajlqjzrcxd
47:59
以上就是关于问题小美拿到了一个长度为的字符串，她希望将字符串从左到右平铺成一个矩阵（先平铺第一行，然后是第二行，以此类推，矩阵有行列，必须保证，即每个字符换行，共行）。
该矩阵的权值定义为这个矩阵的连通块数量。小美希望最终矩阵的权值尽可能小，你能帮小美求出这个最小权值吗？
注：我们定义，上下左右四个方向相邻的相同字符是连通的。的答案
欢迎关注区块链毕设网-
专业区块链毕业设计成品源码，定制。
区块链NFT链游项目方科学家脚本开发培训
