文章目录
前言
解题思路
前言
N * M的棋盘
每种颜色的格子数必须相同的
上下左右的格子算相邻
相邻格子染的颜色必须不同
所有格子必须染色
返回至少多少种颜色可以完成任务
解题思路
写暴力方法观察规律
尝试1种颜色能不能完成
尝试2种颜色能不能完成
最多有n*m种
public static int minColors(int N, int M) {
// 颜色数量是i
for (int i = 2; i < N * M; i++) {
int[][] matrix = new int[N][M];
// 下面这一句可知，需要的最少颜色数i，一定是N*M的某个因子
if ((N * M) % i == 0 && can(matrix, N, M, i)) {
return i;
}
}
return N * M;
}
// 在matrix上染色，返回只用pNum种颜色是否可以做到要求
public static boolean can(int[][] matrix, int N, int M, int pNum) {
int all = N * M;
int every = all / pNum;
ArrayList<Integer> rest = new ArrayList<>();
rest.add(0);
for (int i = 1; i <= pNum; i++) {
rest.add(every);
}
return process(matrix, N, M, pNum, 0, 0, rest);
}
public static boolean process(int[][] matrix, int N, int M, int pNum, int row, int col, List<Integer> rest) {
if (row == N) {
return true;
}
if (col == M) {
return process(matrix, N, M, pNum, row + 1, 0, rest);
}
int left = col == 0 ? 0 : matrix[row][col - 1];
int up = row == 0 ? 0 : matrix[row - 1][col];
for (int color = 1; color <= pNum; color++) {
if (color != left && color != up && rest.get(color) > 0) {
int count = rest.get(color);
rest.set(color, count - 1);
matrix[row][col] = color;
if (process(matrix, N, M, pNum, row, col + 1, rest)) {
return true;
}
rest.set(color, count);
matrix[row][col] = 0;
}
}
return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
根据输出规律,我们不难推出是最小颜色是N*M最小的质数因子
