这题用ida*
1.估价为8-最多的数的个数
2.记录上一次的操作,如果上一次选了A这一次就不能选F了,其他同理
这道题的代码有点难打。。。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int a[11][11], flag; char ans[30];
pair<int, int> get() {
int maxx = 0, p;
for (int i = 1; i <= 3; i++) {
int now = 0;
for (int j = 3; j <= 5; j++) now += (a[3][j] == i);
if (a[4][3] == i) now++; if (a[4][5] == i) now++;
for (int j = 3; j <= 5; j++) now += (a[5][j] == i);
if (now > maxx) maxx = now, p = i;
}
return make_pair(8 - maxx, p);
}
bool dfs(int k) {
pair<int, int> o = get();
int cnt = o.first;
if (!cnt) {
for (int i = 0; i < k; i++) putchar(ans[i]);
puts(k ? "" : "No moves needed");
printf("%d\n", o.second);
return 1;
}
if (k + cnt > flag) return 0;
char ch;
if (!k || ans[k - 1] != 'F') {
ans[k] = 'A';
ch = a[1][3];
for (int i = 2; i <= 7; i++) a[i - 1][3] = a[i][3];
a[7][3] = ch;
if (dfs(k + 1)) return 1;
ans[k] = 0;
ch = a[7][3];
for (int i = 7; i >= 2; i--) a[i][3] = a[i - 1][3];
a[1][3] = ch;
}
if (!k || ans[k - 1] != 'E') {
ans[k] = 'B';
ch = a[1][5];
for (int i = 2; i <= 7; i++) a[i - 1][5] = a[i][5];
a[7][5] = ch;
if (dfs(k + 1)) return 1;
ans[k] = 0;
ch = a[7][5];
for (int i = 7; i >= 2; i--) a[i][5] = a[i - 1][5];
a[1][5] = ch;
}
if (!k || ans[k - 1] != 'H') {
ans[k] = 'C';
ch = a[3][7];
for (int i = 7; i >= 2; i--) a[3][i] = a[3][i - 1];
a[3][1] = ch;
if (dfs(k + 1)) return 1;
ans[k] = 0;
ch = a[3][1];
for (int i = 2; i <= 7; i++) a[3][i - 1] = a[3][i];
a[3][7] = ch;
}
if (!k || ans[k - 1] != 'G') {
ans[k] = 'D';
ch = a[5][7];
for (int i = 7; i >= 2; i--) a[5][i] = a[5][i - 1];
a[5][1] = ch;
if (dfs(k + 1)) return 1;
ans[k] = 0;
ch = a[5][1];
for (int i = 2; i <= 7; i++) a[5][i - 1] = a[5][i];
a[5][7] = ch;
}
if (!k || ans[k - 1] != 'B') {
ans[k] = 'E';
ch = a[7][5];
for (int i = 7; i >= 2; i--) a[i][5] = a[i - 1][5];
a[1][5] = ch;
if (dfs(k + 1)) return 1;
ans[k] = 0;
ch = a[1][5];
for (int i = 2; i <= 7; i++) a[i - 1][5] = a[i][5];
a[7][5] = ch;
}
if (!k || ans[k - 1] != 'A') {
ans[k] = 'F';
ch = a[7][3];
for (int i = 7; i >= 2; i--) a[i][3] = a[i - 1][3];
a[1][3] = ch;
if (dfs(k + 1)) return 1;
ans[k] = 0;
ch = a[1][3];
for (int i = 2; i <= 7; i++) a[i - 1][3] = a[i][3];
a[7][3] = ch;
}
if (!k || ans[k - 1] != 'D') {
ans[k] = 'G';
ch = a[5][1];
for (int i = 2; i <= 7; i++) a[5][i - 1] = a[5][i];
a[5][7] = ch;
if (dfs(k + 1)) return 1;
ans[k] = 0;
ch = a[5][7];
for (int i = 7; i >= 2; i--) a[5][i] = a[5][i - 1];
a[5][1] = ch;
}
if (!k || ans[k - 1] != 'C') {
ans[k] = 'H';
ch = a[3][1];
for (int i = 2; i <= 7; i++) a[3][i - 1] = a[3][i];
a[3][7] = ch;
if (dfs(k + 1)) return 1;
ans[k] = 0;
ch = a[3][7];
for (int i = 7; i >= 2; i--) a[3][i] = a[3][i - 1];
a[3][1] = ch;
}
return 0;
}
void solve() {
for (flag = 0; flag <= 24; flag++)
if (dfs(0)) return;
}
int main() {
while (~scanf("%d", &a[1][3]) && a[1][3]) {
scanf("%d", &a[1][5]);
scanf("%d%d", &a[2][3], &a[2][5]);
for (int i = 1; i <= 7; i++) scanf("%d", &a[3][i]);
scanf("%d%d", &a[4][3], &a[4][5]);
for (int i = 1; i <= 7; i++) scanf("%d", &a[5][i]);
scanf("%d%d", &a[6][3], &a[6][5]);
scanf("%d%d", &a[7][3], &a[7][5]);
solve();
}
return 0;
}