Poj上是2286
#include <stdio.h>
#include <string.h>
int map[25], deep;
char path[101];
int len;
bool flag;
int f[8][7] = { //狀態轉移數組
{ 1, 3, 7, 12, 16, 21, 23 },
{ 2, 4, 9, 13, 18, 22, 24 },
{ 11, 10, 9, 8, 7, 6, 5 },
{ 20, 19, 18, 17, 16, 15, 14 },
{ 24, 22, 18, 13, 9, 4, 2 },
{ 23, 21, 16, 12, 7, 3, 1 },
{ 14, 15, 16, 17, 18, 19, 20 },
{ 5, 6, 7, 8, 9, 10, 11 }
};
inline int max(int a, int b)
{return a>b?a:b;}
void out() //輸出路徑
{
int i;
for(i = 0; i < len; ++ i)
printf("%c",path[i]);
puts("");
printf("%d\n",map[7]);
}
inline int cal() //A*
{
int num[4] = {0, 0, 0, 0};
num[map[7]] ++; num[map[8]] ++; num[map[9]] ++;
num[map[12]] ++; num[map[13]] ++;
num[map[16]] ++; num[map[17]] ++; num[map[18]] ++;
return 8 - max(max(num[1], num[2]), num[3]);
}
inline bool ok() //判斷是否達到目標態
{
int x = map[7], i;
if(map[8]^x | map[9]^x | map[12]^x | map[13]^x |
map[16]^x | map[17]^x | map[18]^x)
return false;
return true;
}
int astar;
void dfs(int dep) //IDA*
{
int temp[25], J;
if(dep == deep)
{
if(ok()) flag = true;
return ;
}
for(int i = 0; i < 8; ++ i)
{
for(J = 1; J < 25; ++ J)temp[J] = map[J];
//狀態轉移
for(J = 0; J < 6; ++ J)
map[f[i][J]] = temp[f[i][J + 1]];
map[f[i][6]] = temp[f[i][0]];
astar = cal();
if(deep > dep + astar)
{
path[len ++] = i + 'A';
dfs(dep + 1);
if(flag)return;
len --;
}
for(J = 1; J < 25; ++ J)map[J] = temp[J];
}
}
int main()
{
while(scanf("%d", &map[1]), map[1])
{
for(int i = 2; i < 25; ++ i) scanf("%d", &map[i]);
if(ok())
{
printf("No moves needed\n%d\n", map[7]);
continue;
}
len = 0; deep = 1;
flag = false;
while(!flag)
{
dfs(0);
deep ++;
}
out();
}
}