2021-08-29：N * M的棋盘（N和M是输入参数），每种颜色的格子数必须相同的，上下左右的格子算相邻，相邻格子染的颜色必须不同，所有格子必须染色，返回至少多少种颜色可以完成任务。 福大大 答

2021-08-29：N * M的棋盘（N和M是输入参数），每种颜色的格子数必须相同的，上下左右的格子算相邻，相邻格子染的颜色必须不同，所有格子必须染色，返回至少多少种颜色可以完成任务。

福大大 答案2021-08-29：

1.暴力法，看规律。
2.数学法。规律是N*M最小的质数因子就是需要的返回值。

代码用golang编写。代码如下：

package mainimport "fmt"func main() {ret := minColors(4, 2)fmt.Println(ret)
}// N * M的棋盘
// 每种颜色的格子数必须相同的
// 相邻格子染的颜色必须不同
// 所有格子必须染色
// 返回至少多少种颜色可以完成任务func minColors(N int, M int) int {// 颜色数量是ifor i := 2; i < N*M; i++ {matrix := make([][]int, N)for i := 0; i < N; i++ {matrix[i] = make([]int, M)}// 下面这一句可知，需要的最少颜色数i，一定是N*M的某个因子if (N*M)%i == 0 && can(matrix, N, M, i) {return i}}return N * M
}// 在matrix上染色，返回只用pNum种颜色是否可以做到要求
func can(matrix [][]int, N int, M int, pNum int) bool {all := N * Mevery := all / pNumrest := make([]int, 0)rest = append(rest, 0)for i := 1; i <= pNum; i++ {rest = append(rest, every)}return process(matrix, N, M, pNum, 0, 0, rest)
}func process(matrix [][]int, N int, M int, pNum int, row int, col int, rest []int) bool {if row == N {return true}if col == M {return process(matrix, N, M, pNum, row+1, 0, rest)}left := 0if col != 0 {left = matrix[row][col-1]}up := 0if row != 0 {up = matrix[row-1][col]}for color := 1; color <= pNum; color++ {if color != left && color != up && rest[color] > 0 {count := rest[color]rest[color] = count - 1matrix[row][col] = colorif process(matrix, N, M, pNum, row, col+1, rest) {return true}rest[color] = countmatrix[row][col] = 0}}return false
}func twoSelectOne(c bool, a int, b int) int {if c {return a} else {return b}
}

执行结果如下：

左神java代码