一稽亏、問(wèn)題描述
地圖上某些區(qū)域挨著，挨著的區(qū)域不能是相同的顏色缕题，如果使用m中材料對(duì)地圖著色截歉，共有多少種著色方式
二、解決思路
地圖可以看做是圖烟零，地圖上的位置相當(dāng)于圖上的點(diǎn)瘪松，如果挨著代表點(diǎn)與點(diǎn)之間有邊，否則沒(méi)有锨阿，使用回溯發(fā)宵睦，確定限界條件個(gè)剪枝函數(shù)，不過(guò)當(dāng)前問(wèn)題是求解所有的方案墅诡，所以沒(méi)有必要需要剪枝函數(shù)壳嚎。當(dāng)問(wèn)題到達(dá)子節(jié)點(diǎn)則代表是一個(gè)可行解。到達(dá)之后進(jìn)行回溯末早，求解其他的方案烟馅。
clipboard.png
三、代碼
public class MapColoring {
public static void main(String[] args) {
//鄰接矩陣存儲(chǔ)圖 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},
};
//記錄所有的結(jié)果
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 所有的結(jié)果集
* @param i 當(dāng)前點(diǎn)
*/
public static int coloring(int[][] adjacencyMatrix, int[][] allResult, int i, int[] currentValue, int color, int resultIndex) {
/**
* 判斷當(dāng)前節(jié)點(diǎn)的著色
* 循環(huán)已經(jīng)著色的點(diǎn) ,如果相連則判斷能否著色當(dāng)前顏色
* 循環(huán)顏色
*/
if (i > adjacencyMatrix.length - 1) {
//將當(dāng)前結(jié)果保存到全部結(jié)果中
for (int j = 0; j < currentValue.length; j++) {
allResult[resultIndex][j] = currentValue[j];
}
resultIndex += 1;
return resultIndex;
}
for (int j = 1; j <= color; j++) {
// 記錄當(dāng)前節(jié)點(diǎn)的顏色嘗試
if (isOk(adjacencyMatrix, j, currentValue, i)) {
// 當(dāng)前節(jié)點(diǎn)染色j
currentValue[i] = j;
//向下遞歸 如果這條路最終能走到葉子節(jié)點(diǎn)然磷，則會(huì)加入到allResult
resultIndex = coloring(adjacencyMatrix, allResult, i + 1, currentValue, color, resultIndex);
//由于這里是for循環(huán)嘗試其他的道路，所以不用手動(dòng)回溯姿搜，下次currentValue[i] = j; 會(huì)將本次循環(huán)值覆蓋痪欲，直到達(dá)到葉子節(jié)點(diǎn)保存結(jié)果
}
}
return resultIndex;
}
/**
* 判斷當(dāng)前節(jié)點(diǎn)是否可以進(jìn)行找色
* 循環(huán)已經(jīng)作色的點(diǎn) 當(dāng)相鄰再判斷顏色是否相等
*
* @param adjacencyMatrix 鄰接矩陣
* @param colorIndex 判斷的顏色
* @param currentValue 當(dāng)前值列表
* @param i 當(dāng)前節(jié)點(diǎn)
* @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;
}
