网站系统制作教程视频教程,关于自行建设门户网站的请示,wordpress语言,评估网站建设方案GitHub - jzplp/aoapc-UVA-Answer: 算法竞赛入门经典 例题和习题答案 刘汝佳 第二版
题目其实不难#xff0c;但是耗费了我较多时间。
这种题关键就是在于找到约束条件#xff0c;我在DFS的基础上#xff0c;试了很多种策略#xff1a;
1. 对3种数字#xff0c;每种数字…GitHub - jzplp/aoapc-UVA-Answer: 算法竞赛入门经典 例题和习题答案 刘汝佳 第二版
题目其实不难但是耗费了我较多时间。
这种题关键就是在于找到约束条件我在DFS的基础上试了很多种策略
1. 对3种数字每种数字递归遍历一次这样每次只需要关注一种数字的变化情况更少。
2. 使用一个long long类型的数字作为map的keykey表示这种数字在图形中分别的位置value表示在第几步访问过。如果重复访问且步数更长则不继续递归。
3. 使用剪枝策略认为不符合情况结点不继续遍历。但是我想的剪枝方法不合理使用了之后是错误的在最后有给出
4. 迭代加深搜索一层一层更深的查找。适用于本题次数最少的要求。
5. 乐观估价函数在中心每个点的值不对的情况下每个点都至少需要一次移动才能正确。因此估价函数为 不正确的点数现有的步数 要求的最大步数。 上述的方法是结合使用的一开始没想到估价函数一直在剪枝策略中纠结然后一直超时。最后换成了估价函数时间瞬间缩短了。
虽然移动的可能性是无限的但是最多的移动次数也就是十几次。 AC代码
#includestdio.h
#includemap
#includestring.h#define MAXLEN 15using namespace std;int arr[24];
int arrCon[4][7];
// 是否访问过的记录
maplong 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[i1];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, stepCount1, 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(i1);mp[sum] 0;moveCount[i] getValue(i1, 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;
}
