GitHub – jzplp/aoapc-UVA-Answer: 算法竞赛入门经典 例题和习题答案 刘汝佳 第二版
题目其实不难，但是耗费了我较多时间。
这种题关键就是在于找到约束条件，我在DFS的基础上，试了很多种策略：
1. 对3种数字，每种数字递归遍历一次，这样每次只需要关注一种数字的变化，情况更少。
2. 使用一个long long类型的数字作为map的key，key表示这种数字在图形中分别的位置，value表示在第几步访问过。如果重复访问且步数更长，则不继续递归。
3. 使用剪枝策略，认为不符合情况结点不继续遍历。（但是我想的剪枝方法不合理，使用了之后是错误的，在最后有给出）
4. 迭代加深搜索，一层一层更深的查找。适用于本题次数最少的要求。
5. 乐观估价函数：在中心每个点的值不对的情况下，每个点都至少需要一次移动才能正确。因此估价函数为 不正确的点数+现有的步数 <= 要求的最大步数。
上述的方法是结合使用的，一开始没想到估价函数，一直在剪枝策略中纠结，然后一直超时。最后换成了估价函数，时间瞬间缩短了。
虽然移动的可能性是无限的，但是最多的移动次数也就是十几次。
AC代码
#include#include
错误的剪枝策略：（不要使用））
// 错误的剪枝策略，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;}