前言

N * M的棋盘
The number of squares for each color must be the same
The upper, lower, left and right grids are considered adjacent
Adjacent squares must be dyed in different colors
All lattices must be dyed
Returns at least how many colors to complete the task

解题思路

Write the law of violence method observation

尝试1color can be completed
尝试2color can be completed
最多有n*m种

public static int minColors(int N, int M) {
    
		// The number of colors isi
		for (int i = 2; i < N * M; i++) {
    
			int[][] matrix = new int[N][M];
			// The following sentence is known,The minimum number of colors requiredi,一定是N*M的某个因子
			if ((N * M) % i == 0 && can(matrix, N, M, i)) {
    
				return i;
			}
		}
		return N * M;
	}

	// 在matrixdyeing,Return onlypNumWhether the color can meet the requirements
	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;
	}

According to the output law,It is not difficult for us to deduce that the minimum color isN*M最小的质数因子