IDA*算法，即迭代加深的A*算法。实际上就是迭代加深+DFS+估价函数
题目传送：The Rotation Game
AC代码：
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <sstream>
#include <utility>
#include <iostream>
#include <algorithm>
#include <functional>
#define LL long long
#define INF 0x7fffffff
using namespace std;
int mp[25];
int n;
int pos[] = {7, 8, 9, 12, 13, 16, 17, 18};
int depth;
int ans_num;
char ans[205];
bool is_ok(int *g) {//推断是否已达到结果
int t = g[7];
if(t == g[8] && t == g[9] && t == g[12] && t == g[13] && t == g[16] && t == g[17] && t == g[18]) {
return true;
}
return false;
}
void change_state(int *g, int a1, int a2, int a3, int a4, int a5, int a6, int a7) {//状态转换（这里就是数字移位）
int tmp = g[a1];
g[a1] = g[a2]; g[a2] = g[a3]; g[a3] = g[a4];
g[a4] = g[a5]; g[a5] = g[a6]; g[a6] = g[a7];
g[a7] = tmp;
}
int get_maxnum(int *g) {//获取中间8个数之间出现次数最大的那个数的次数
int cnt[4];
cnt[1] = cnt[2] = cnt[3] = 0;
for(int i = 0; i < 8; i ++) {
cnt[g[pos[i]]] ++;
}
return max(cnt[1], max(cnt[2], cnt[3]));
}
//IDA*算法的核心即为DFS+迭代加深+估价函数
int dfs(int *g, int cur_depth, int pre_dir) {
if(depth - cur_depth < 8 - get_maxnum(g)) { //相似于估价函数，此处由于每次数字移位最多仅仅能使得中间的数字多一个一样的。
return 0; //而每次搜索相应一次数字移位。而当搜索次数小于8个数中要改变得几个数时。肯定不正确。
剪枝①
}
if(cur_depth >= depth) {//迭代加深搜索的精髓
return 0;
}
int tmp[25];
for(int i = 1; i <= 8; i ++) {//往八个方向搜索
if((i == 1 && pre_dir == 6) || (i == 6 && pre_dir == 1)) continue;//下面都是减去和前一个移位的方向相反方向的情况。剪枝②
if((i == 2 && pre_dir == 5) || (i == 5 && pre_dir == 2)) continue;
if((i == 3 && pre_dir == 8) || (i == 8 && pre_dir == 3)) continue;
if((i == 4 && pre_dir == 7) || (i == 7 && pre_dir == 4)) continue;
for(int j = 1; j <= 24; j ++) tmp[j] = g[j];
switch(i) {
case 1: ans[cur_depth] = 'A'; change_state(tmp, 1, 3, 7, 12, 16, 21, 23); break;
case 2: ans[cur_depth] = 'B'; change_state(tmp, 2, 4, 9, 13, 18, 22, 24); break;
case 3: ans[cur_depth] = 'C'; change_state(tmp, 11, 10, 9, 8, 7, 6, 5); break;
case 4: ans[cur_depth] = 'D'; change_state(tmp, 20, 19, 18, 17, 16, 15, 14); break;
case 5: ans[cur_depth] = 'E'; change_state(tmp, 24, 22, 18, 13, 9, 4, 2); break;
case 6: ans[cur_depth] = 'F'; change_state(tmp, 23, 21, 16, 12, 7, 3, 1); break;
case 7: ans[cur_depth] = 'G'; change_state(tmp, 14, 15, 16, 17, 18, 19, 20); break;
case 8: ans[cur_depth] = 'H'; change_state(tmp, 5, 6, 7, 8, 9, 10, 11); break;
}
if(is_ok(tmp)) {
ans_num = tmp[7];
ans[cur_depth + 1] = '\0';
return 1;
}
if(dfs(tmp, cur_depth + 1, i)) return 1;
}
return 0;
}
int main() {
int x;
while(1) {
scanf("%d", &mp[1]);
if(mp[1] == 0) {
break;
}
for(int i = 2; i <= 24; i ++) {
scanf("%d", &mp[i]);
}
if(is_ok(mp)) {
printf("No moves needed\n");
printf("%d\n", mp[7]);
continue;
}
depth = 1;
while(1) {
if(dfs(mp, 0, -1)) {
break;
}
depth ++;
}
printf("%s\n", ans);
printf("%d\n", ans_num);
}
return 0;
}