GitHub - jzplp/aoapc-UVA-Answer: 算法競賽入門經(jīng)典 例題和習(xí)題答案 劉汝佳 第二版

題目其實不難，但是耗費了我較多時間。

這種題關(guān)鍵就是在于找到約束條件，我在DFS的基礎(chǔ)上，試了很多種策略：

1. 對3種數(shù)字，每種數(shù)字遞歸遍歷一次，這樣每次只需要關(guān)注一種數(shù)字的變化，情況更少。

2. 使用一個long long類型的數(shù)字作為map的key，key表示這種數(shù)字在圖形中分別的位置，value表示在第幾步訪問過。如果重復(fù)訪問且步數(shù)更長，則不繼續(xù)遞歸。

3. 使用剪枝策略，認(rèn)為不符合情況結(jié)點不繼續(xù)遍歷。（但是我想的剪枝方法不合理，使用了之后是錯誤的，在最后有給出）

4. 迭代加深搜索，一層一層更深的查找。適用于本題次數(shù)最少的要求。

5. 樂觀估價函數(shù)：在中心每個點的值不對的情況下，每個點都至少需要一次移動才能正確。因此估價函數(shù)為 不正確的點數(shù)+現(xiàn)有的步數(shù) <= 要求的最大步數(shù)。

上述的方法是結(jié)合使用的，一開始沒想到估價函數(shù)，一直在剪枝策略中糾結(jié)，然后一直超時。最后換成了估價函數(shù)，時間瞬間縮短了。

雖然移動的可能性是無限的，但是最多的移動次數(shù)也就是十幾次。

AC代碼

#include<stdio.h>
#include<map> 
#include<string.h>#define MAXLEN 15using namespace std;int arr[24];
int arrCon[4][7];
// 是否訪問過的記錄
map<long long, int> mp;
// 記錄三種數(shù)字完成時的移動情況 
char moves[3][MAXLEN + 5];
// 移動數(shù)組的長度 
int moveCount[3];
// 每個移動數(shù)組代表的移動類型（可能并不是下表所指示的那個） 
int moveType[3];// 從輸入數(shù)據(jù)轉(zhuǎn)換為四數(shù)組模式 
void convertArr() {int i;arrCon[0][0] = arr[0]; arrCon[1][0] = arr[1];arrCon[0][1] = arr[2]; arrCon[1][1] = arr[3];for(i = 0; i < 7; ++i) arrCon[2][i] = arr[4 + i];arrCon[0][2] = arr[6]; arrCon[1][2] = arr[8];arrCon[0][3] = arr[11]; arrCon[1][3] = arr[12];for(i = 0; i < 7; ++i) arrCon[3][i] = arr[13 + i];arrCon[0][4] = arr[15]; arrCon[1][4] = arr[17];arrCon[0][5] = arr[20]; arrCon[1][5] = arr[21];arrCon[0][6] = arr[22]; arrCon[1][6] = arr[23];
}// 對一個數(shù)組移動位置 type->0 往大移動 type->1 往小移動
void moveArr(int *arrSrc, int type) {int t, i;if(type == 0) {t = arrSrc[6];for(i = 6; i > 0; --i) arrSrc[i] = arrSrc[i-1];arrSrc[0] = t;} else {t = arrSrc[0];for(i = 0; i < 6; ++i) arrSrc[i] = arrSrc[i+1];arrSrc[6] = t;}
}// 按照某個方向移動  flag->1 移動 flag->0 恢復(fù)移動 
void moveStep(int num, bool flag) {bool type;switch(num) {case 0:case 5:type = num < 4 ? 1 : 0;type = flag ? type : !type;moveArr(arrCon[0], type);arrCon[2][2] = arrCon[0][2];arrCon[3][2] = arrCon[0][4];break;case 1:case 4:type = num < 4 ? 1 : 0;type = flag ? type : !type;moveArr(arrCon[1], type);arrCon[2][4] = arrCon[1][2];arrCon[3][4] = arrCon[1][4];break;case 2:case 7:type = num < 4 ? 0 : 1;type = flag ? type : !type;moveArr(arrCon[2], type);arrCon[0][2] = arrCon[2][2];arrCon[1][2] = arrCon[2][4];break;case 3:case 6:type = num < 4 ? 0 : 1;type = flag ? type : !type;moveArr(arrCon[3], type);arrCon[0][4] = arrCon[3][2];arrCon[1][4] = arrCon[3][4];break;}
}// 是否成功 返回成功的字符 否則0 
int isArrive() {int num = arrCon[0][2];if(arrCon[0][3] != num || arrCon[0][4] != num || arrCon[1][2] != num || arrCon[1][3] != num) return 0;if(arrCon[1][4] != num || arrCon[2][3] != num || arrCon[3][3] != num)return 0;return num;
}// 根據(jù)數(shù)字在四數(shù)組中的位置，轉(zhuǎn)換為0-27的數(shù)字?jǐn)?shù)組 
long long getArrPos(int num) {int i, j;long long sum = 0;for(i = 0; i < 4; ++i) {for(j = 0; j < 7; ++j) {if(arrCon[i][j] == num) {if(i < 2) {sum = (sum << 5) + i * 7 + j;} else {if(j == 2 || j == 4) continue;sum = (sum << 5) + i * 7 + j;}}}}return sum;
}// 剪枝
bool shouldMove(int num, int step) {switch(step) {case 0:if(arrCon[0][5] == num || arrCon[0][6] == num || arrCon[0][4] == num) return true;break;case 1:if(arrCon[1][5] == num || arrCon[1][6] == num || arrCon[1][4] == num) return true;break;case 2:if(arrCon[2][0] == num || arrCon[2][1] == num || arrCon[2][2] == num) return true;break;case 3:if(arrCon[3][0] == num || arrCon[3][1] == num || arrCon[3][2] == num) return true;break;case 4:if(arrCon[1][0] == num || arrCon[1][1] == num || arrCon[1][2] == num) return true;break;case 5:if(arrCon[0][0] == num || arrCon[0][1] == num || arrCon[0][2] == num) return true;break;case 6:if(arrCon[3][5] == num || arrCon[3][6] == num || arrCon[3][4] == num) return true;break;case 7:if(arrCon[2][5] == num || arrCon[2][6] == num || arrCon[2][4] == num) return true;break;}return false;
}// 估價函數(shù) true代表有機會 false代表沒機會 
bool hvalue(int num, int stepCount, int k) {int i, j, value = 0;for(i = 0; i < 4; ++i) {if(arrCon[i][3] != num) value += 1;}if(arrCon[0][2] != num) value += 1;if(arrCon[0][4] != num) value += 1;if(arrCon[1][2] != num) value += 1;if(arrCon[1][4] != num) value += 1;return stepCount + value < k;
}//遞歸尋找 
int getValue(int num, int stepCount, int k) {int resArr = isArrive();if(resArr) {moveType[num - 1] = resArr;return stepCount;}if(stepCount >= k) return 0;if(!hvalue(num, stepCount, k))	return 0;int i, count, res;long long sum; // printf(" ------ %d\n", stepCount);for(i = 0; i < 8; ++i) {// if(!shouldMove(num, i)) continue;// 移動moveStep(i, true);// printf(" ----------- %d\n", isFind(num));sum = getArrPos(num);count = mp[sum];if(!count || count > stepCount) {mp[sum] = stepCount;// 記錄步驟 moves[num-1][stepCount] = i;// 訪問子節(jié)點res = getValue(num, stepCount+1, k);if(res) {// 復(fù)位moveStep(i, false); return res;}}// 復(fù)位moveStep(i, false);}return 0;
}int getRes(int k) {int i, j, mini, minV;for(i = 0; i < 3; ++i) {mp.clear();long long sum = getArrPos(i+1);mp[sum] = 0;moveCount[i] = getValue(i+1, 0, k);if(moveCount[i] > 0) k = moveCount[i];// printf("-- %d %d %d \n", k, i, moveCount[i-1]);// moves[i-1][moveCount[i-1]] = 0;}minV = MAXLEN + 10;mini = -1;for(i = 0; i < 3; ++i) {if(moveCount[i] == 0) continue;// printf( "[]%d\n", moveCount[i]);if(minV > moveCount[i]) {minV = moveCount[i];mini = i;} else if(minV == moveCount[i]) {if(strcmp(moves[mini], moves[i]) > 0) {minV = moveCount[i];mini = i;}}}return mini;
}int main() {int i, j, k;while(1) {if(scanf("%d", &arr[0]) != 1 || arr[0] == 0) break;for(i = 1; i < 24; ++i) {scanf("%d", &arr[i]);}convertArr();int resType = isArrive();if(resType) {printf("No moves needed\n");printf("%d\n", resType);continue;}for(i = 1; i < MAXLEN; ++i) {k = getRes(i);if(k >= 0) break;}if(moveCount[k] == 0) {printf("No moves needed\n");} else {for(i = 0; i < moveCount[k]; ++i) {printf("%c", moves[k][i] + 'A');}putchar('\n'); }printf("%d\n", moveType[k]);}return 0;
}

錯誤的剪枝策略：（不要使用））

// 錯誤的剪枝策略，
bool shouldMove(int num, int step) {switch(step) {case 0:if(arrCon[0][5] == num || arrCon[0][6] == num || arrCon[0][4] == num) return true;break;case 1:if(arrCon[1][5] == num || arrCon[1][6] == num || arrCon[1][4] == num) return true;break;case 2:if(arrCon[2][0] == num || arrCon[2][1] == num || arrCon[2][2] == num) return true;break;case 3:if(arrCon[3][0] == num || arrCon[3][1] == num || arrCon[3][2] == num) return true;break;case 4:if(arrCon[1][0] == num || arrCon[1][1] == num || arrCon[1][2] == num) return true;break;case 5:if(arrCon[0][0] == num || arrCon[0][1] == num || arrCon[0][2] == num) return true;break;case 6:if(arrCon[3][5] == num || arrCon[3][6] == num || arrCon[3][4] == num) return true;break;case 7:if(arrCon[2][5] == num || arrCon[2][6] == num || arrCon[2][4] == num) return true;break;}return false;
}