美团笔试第四道,能否帮忙看看哪里有问题
用的DFS,但是只能过60%
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int num = in.nextInt();
int[] nums = new int[num];
String in_ = in.next();
char[] c = in_.toCharArray();
for (int i=0;i<num;i++) {
nums[i] = c[i]-96;
}
List<Integer> x_list = new ArrayList<>();
for (int i=1;i<=num;i++) {
if (num%i==0) {
x_list.add(i);
}
}
int _max = Integer.MAX_VALUE;
for (int x: x_list) {
int y = num/x;
int res = f(x, y, nums);
_max = Math.min(_max, res);
}
System.out.println(_max);
}
public static int f(int x, int y, int[] nums) {
int[][] s = new int[x][y];
int n = 0;
for (int i=0;i<x;i++) {
for (int j=0;j<y;j++) {
s[i][j] = nums[n];
n++;
}
}
int res = 0;
boolean[][] used = new boolean[x][y];
int col = s.length;
int line = s[0].length;
for (int i=0;i<col;i++) {
for (int j = 0; j < line; j++) {
if (!used[i][j]) {
dfs(s, used, i, j);
res++;
}
}
}
return res;
}
public static void dfs(int[][] nums, boolean[][] used, int i, int j) {
if (used[i][j]) return;
int col = nums.length;
int row = nums[0].length;
used[i][j] = true;
if (i + 1 < col && !used[i + 1][j] && nums[i][j] == nums[i + 1][j]) {
dfs(nums, used, i+1, j);
}
if (i - 1 >= 0 && !used[i - 1][j] && nums[i][j] == nums[i - 1][j]) {
dfs(nums, used, i-1, j);
}
if (j + 1 < row && !used[i][j+1] && nums[i][j] == nums[i][j+1]) {
dfs(nums, used, i, j+1);
}
if (j - 1 >= 0 && !used[i][j-1] && nums[i][j] == nums[i][j-1]) {
dfs(nums, used, i, j=1);
}
}
}
#美团##美团笔试#