一、问题描述
地图上某些区域挨着，挨着的区域不能是相同的颜色，如果使用m中材料对地图着色，共有多少种着色方式
二、解决思路
地图可以看做是图，地图上的位置相当于图上的点，如果挨着代表点与点之间有边，否则没有，使用回溯发，确定限界条件个剪枝函数，不过当前问题是求解所有的方案，所以没有必要需要剪枝函数。当问题到达子节点则代表是一个可行解。到达之后进行回溯，求解其他的方案。
clipboard.png
三、代码
public class MapColoring {
public static void main(String[] args) {
//邻接矩阵存储图 0代表相连否则不相连
int[][] adjacencyMatrix = new int[][]{
{0, 1, 1, 1, 0, 0, 0},
{1, 0, 1, 0, 1, 0, 0},
{1, 1, 0, 1, 1, 0, 0},
{1, 0, 1, 0, 1, 0, 1},
{0, 1, 1, 1, 0, 1, 1},
{0, 0, 0, 0, 1, 0, 1},
{0, 0, 0, 1, 1, 1, 0},
};
//记录所有的结果
int[][] allResult = new int[adjacencyMatrix.length][adjacencyMatrix.length];
int[] currentValue = new int[adjacencyMatrix.length];
coloring(adjacencyMatrix, allResult, 0, currentValue, 3, 0);
for (int i = 0; i < allResult.length; i++) {
System.out.println(Arrays.toString(allResult[i]));
}
}
/**
* 地图着色
*
* @param adjacencyMatrix 邻接矩阵
* @param allResult 所有的结果集
* @param i 当前点
*/
public static int coloring(int[][] adjacencyMatrix, int[][] allResult, int i, int[] currentValue, int color, int resultIndex) {
/**
* 判断当前节点的着色
* 循环已经着色的点 ,如果相连则判断能否着色当前颜色
* 循环颜色
*/
if (i > adjacencyMatrix.length - 1) {
//将当前结果保存到全部结果中
for (int j = 0; j < currentValue.length; j++) {
allResult[resultIndex][j] = currentValue[j];
}
resultIndex += 1;
return resultIndex;
}
for (int j = 1; j <= color; j++) {
// 记录当前节点的颜色尝试
if (isOk(adjacencyMatrix, j, currentValue, i)) {
// 当前节点染色j
currentValue[i] = j;
//向下递归 如果这条路最终能走到叶子节点，则会加入到allResult
resultIndex = coloring(adjacencyMatrix, allResult, i + 1, currentValue, color, resultIndex);
//由于这里是for循环尝试其他的道路，所以不用手动回溯，下次currentValue[i] = j; 会将本次循环值覆盖，直到达到叶子节点保存结果
}
}
return resultIndex;
}
/**
* 判断当前节点是否可以进行找色
* 循环已经作色的点 当相邻再判断颜色是否相等
*
* @param adjacencyMatrix 邻接矩阵
* @param colorIndex 判断的颜色
* @param currentValue 当前值列表
* @param i 当前节点
* @return
*/
public static boolean isOk(int[][] adjacencyMatrix, int colorIndex, int[] currentValue, int i) {
for (int j = 0; j < i; j++) {
if (adjacencyMatrix[j][i] == 1) {
if (currentValue[j] == colorIndex) {
return false;
}
}
}
return true;
}
