2021-08-29：N * M的棋盘（N和M是输入参数），每种颜色的格子数必须相同的，上下左右的格子算相邻，相邻格子染的颜色必须不同，所有格子必须染色，返回至少多少种颜色可以完成任务。
福大大 答案2021-08-29：
1.暴力法，看规律。
2.数学法。规律是N*M最小的质数因子就是需要的返回值。
代码用golang编写。代码如下：
package main
import "fmt"
func main() {
ret := minColors(4, 2)
fmt.Println(ret)
}
// N * M的棋盘
// 每种颜色的格子数必须相同的
// 相邻格子染的颜色必须不同
// 所有格子必须染色
// 返回至少多少种颜色可以完成任务
func minColors(N int, M int) int {
// 颜色数量是i
for 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 * M
every := all / pNum
rest := 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 := 0
if col != 0 {
left = matrix[row][col-1]
}
up := 0
if 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 - 1
matrix[row][col] = color
if process(matrix, N, M, pNum, row, col+1, rest) {
return true
}
rest[color] = count
matrix[row][col] = 0
}
}
return false
}
func twoSelectOne(c bool, a int, b int) int {
if c {
return a
} else {
return b
}
}
执行结果如下：
左神java代码
