UVA-1343 旋转游戏 题解答案代码 算法竞赛入门经典第二版

GitHub - jzplp/aoapc-UVA-Answer: 算法竞赛入门经典 例题和习题答案 刘汝佳 第二版

题目其实不难，但是耗费了我较多时间。

这种题关键就是在于找到约束条件，我在DFS的基础上，试了很多种策略：

1. 对3种数字，每种数字递归遍历一次，这样每次只需要关注一种数字的变化，情况更少。

2. 使用一个long long类型的数字作为map的key，key表示这种数字在图形中分别的位置，value表示在第几步访问过。如果重复访问且步数更长，则不继续递归。

3. 使用剪枝策略，认为不符合情况结点不继续遍历。（但是我想的剪枝方法不合理，使用了之后是错误的，在最后有给出）

4. 迭代加深搜索，一层一层更深的查找。适用于本题次数最少的要求。

5. 乐观估价函数：在中心每个点的值不对的情况下，每个点都至少需要一次移动才能正确。因此估价函数为 不正确的点数+现有的步数 <= 要求的最大步数。

上述的方法是结合使用的，一开始没想到估价函数，一直在剪枝策略中纠结，然后一直超时。最后换成了估价函数，时间瞬间缩短了。

虽然移动的可能性是无限的，但是最多的移动次数也就是十几次。

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;
// 记录三种数字完成时的移动情况 
char moves[3][MAXLEN + 5];
// 移动数组的长度 
int moveCount[3];
// 每个移动数组代表的移动类型（可能并不是下表所指示的那个） 
int moveType[3];// 从输入数据转换为四数组模式 
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];
}// 对一个数组移动位置 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 恢复移动 
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;
}// 根据数字在四数组中的位置，转换为0-27的数字数组 
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;
}// 估价函数 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;// 访问子节点res = getValue(num, stepCount+1, k);if(res) {// 复位moveStep(i, false); return res;}}// 复位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;
}