搭建网站用什么框架,个人网站建设方案书,用自己电脑做网站空间,蜘蛛不抓取网站的原因小美拿到了一个长度为n的字符串#xff0c;她希望将字符串从左到右平铺成一个矩阵#xff08;先平铺第一行#xff0c;然后是第二行#xff0c;以此类推#xff0c;矩阵有x行y列#xff0c;必须保证x∗yn#xff0c;即每y个字符换行#xff0c;共x行#xff09;。
该…小美拿到了一个长度为n的字符串她希望将字符串从左到右平铺成一个矩阵先平铺第一行然后是第二行以此类推矩阵有x行y列必须保证x∗yn即每y个字符换行共x行。
该矩阵的权值定义为这个矩阵的连通块数量。小美希望最终矩阵的权值尽可能小你能帮小美求出这个最小权值吗
注我们定义上下左右四个方向相邻的相同字符是连通的。
输入描述
第一行输入一个正整数n代表字符串的长度。
第二行输入一个长度为n的、仅由小写字母组成的字符串。
1n10000输出描述
输出一个整数表示最小权值。示例1
输入例子
9
aababbabb输出例子
2例子说明
平铺为3*3的矩阵
aab
abb
abb
共有2个连通块4个a和5个b。private static final int[][] DIRECTIONS {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};private static void dfs(char[][] block, boolean[][] visited, int i, int j, int x, int y) {visited[i][j] true;for (int[] direction : DIRECTIONS) {int ni i direction[0], nj j direction[1];if (ni 0 nj 0 ni x nj y !visited[ni][nj] block[i][j] block[ni][nj]) {dfs(block, visited, ni, nj, x, y);}}
}public static void main(String[] args) throws Exception {Scanner sc new Scanner(System.in);int n sc.nextInt();sc.nextLine();//需要读取并丢弃剩余的换行符!因为scanner.nextInt()方法只读取整数,不读取后面的换行符String str sc.nextLine();//scanner.nextLine()会读取整行的输入包括空格,直到遇到换行符 scanner.next()则只会读取一个单词,即直到遇到空格或换行符。//先根据n求出所有可能的x和yint ans 10005, sqrt (int) Math.sqrt(n);ArrayListint[] list new ArrayList();for (int i 1; i sqrt; i) {if (n % i 0) {list.add(new int[]{i, n / i});list.add(new int[]{n / i, i});}}if (sqrt * sqrt n) list.remove(list.size() - 1);//根据所有的x和y来构建矩阵for (int[] ints : list) {int x ints[0], y ints[1], block_num 0;char[][] block new char[x][y];//矩阵boolean[][] visited new boolean[x][y];//标记矩阵每个点是否被检查过for (int i 0; i x; i) {for (int j 0; j y; j) {block[i][j] str.charAt(i * y j);}}//根据构建的矩阵求出最小连通量for (int i 0; i x; i) {for (int j 0; j y; j) {if (!visited[i][j]) {dfs(block, visited, i, j, x, y);block_num;}}}ans Math.min(ans, block_num);}System.out.println(ans);
}
