HDU_1043
老大之前让我研究了一下构造不限定步数的八数码的解，而自己苦于没有可行的套路迟迟没有用代码实现出来，今天又交流了一下忽然顿悟到如果把空位每次都固定在一个位置然后再枚举需要动的数字就可以比较容易地用代码实现出来了。其实后来才发现，也只是想起来容易，敲起来一样很复杂，搞了几个小时才完工-_-||。由于没有去写基本操作的小函数导致代码又臭又长，还出了几个错误导致调了几个小时，回头再和老大一块精简下代码吧。
#include<stdio.h>
#include<string.h>
char q[1010], b[5];
int p, g[10];
void init()
{
int i;
if(b[0] == 'x')
g[0] = 0;
else
g[0] = b[0] - '0';
for(i = 1; i < 9; i ++)
{
scanf("%s", b);
if(b[0] == 'x')
g[i] = 0;
else
g[i] = b[0] - '0';
}
}
void solve()
{
int i, j, k;
char u = 'u', d = 'd', l = 'l', r = 'r';
p = 0;
//(1) blank ready
if(!g[0])
{
q[p ++] = d; q[p ++] = r;
g[0] = g[3], g[3] = g[4], g[4] = 0;
}
else if(!g[1])
{
q[p ++] = d;
g[1] = g[4], g[4] = 0;
}
else if(!g[2])
{
q[p ++] = d; q[p ++] = l;
g[2] = g[5], g[5] = g[4], g[4] = 0;
}
else if(!g[3])
{
q[p ++] = r;
g[3] = g[4], g[4] = 0;
}
else if(!g[5])
{
q[p ++] = l;
g[5] = g[4], g[4] = 0;
}
else if(!g[6])
{
q[p ++] = r; q[p ++] = u;
g[6] = g[7], g[7] = g[4], g[4] = 0;
}
else if(!g[7])
{
q[p ++] = u;
g[7] = g[4], g[4] = 0;
}
else if(!g[8])
{
q[p ++] = l; q[p ++] = u;
g[8] = g[7], g[7] = g[4], g[4] = 0;
}
//(2) 3 ready
if(g[1] == 3)
{
q[p ++] = l; q[p ++] = u; q[p ++] = r; q[p ++] = d;
g[4] = g[0]; g[0] = g[1]; g[1] = g[3]; g[3] = g[4]; g[4] = g[0];
}
else if(g[2] == 3)
{
q[p ++] = u; q[p ++] = r; q[p ++] = d; q[p ++] = l;
q[p ++] = l; q[p ++] = u; q[p ++] = r; q[p ++] = d;
g[4] = g[0]; g[0] = g[2]; g[2] = g[5]; g[5] = g[1]; g[1] = g[3]; g[3] = g[4]; g[4] = 0;
}
else if(g[3] == 3)
{
q[p ++] = u; q[p ++] = l; q[p ++] = d; q[p ++] = r;
g[4] = g[0]; g[0] = g[3]; g[3] = g[1]; g[1] = g[4]; g[4] = 0;
}
else if(g[5] == 3)
{
q[p ++] = r; q[p ++] = u; q[p ++] = l; q[p ++] = d;
q[p ++] = l; q[p ++] = u; q[p ++] = r; q[p ++] = d;
g[4] = g[0]; g[0] = g[5]; g[5] = g[2]; g[2] = g[1]; g[1] = g[3]; g[3] = g[4]; g[4] = 0;
}
else if(g[6] == 3)
{
q[p ++] = l; q[p ++] = d; q[p ++] = r; q[p ++] = u;
q[p ++] = u; q[p ++] = l; q[p ++] = d; q[p ++] = r;
g[4] = g[0]; g[0] = g[6]; g[6] = g[7]; g[7] = g[3]; g[3] = g[1]; g[1] = g[4]; g[4] = 0;
}
else if(g[7] == 3)
{
q[p ++] = d; q[p ++] = l; q[p ++] = u; q[p ++] = r;
q[p ++] = u; q[p ++] = l; q[p ++] = d; q[p ++] = r;
g[4] = g[0]; g[0] = g[7]; g[7] = g[6]; g[6] = g[3]; g[3] = g[1]; g[1] = g[4]; g[4] = 0;
}
else if(g[8] == 3)
{
q[p ++] = d; q[p ++] = r; q[p ++] = u; q[p ++] = l;
q[p ++] = d; q[p ++] = l; q[p ++] = u; q[p ++] = r;
q[p ++] = u; q[p ++] = l; q[p ++] = d; q[p ++] = r;
g[4] = g[0]; g[0] = g[8]; g[8] = g[5]; g[5] = g[7]; g[7] = g[6]; g[6] = g[3]; g[3] = g[1]; g[1] = g[4]; g[4] = 0;
}
//(3) 2 ready
if(g[1] == 2)
{
q[p ++] = u; q[p ++] = r; q[p ++] = d; q[p ++] = l;
q[p ++] = r; q[p ++] = d; q[p ++] = l; q[p ++] = u;
q[p ++] = d; q[p ++] = l; q[p ++] = u; q[p ++] = r;
g[4] = g[1]; g[1] = g[2]; g[2] = g[5]; g[5] = g[8]; g[8] = g[7]; g[7] = g[6]; g[6] = g[3]; g[3] = g[4]; g[4] = 0;
}
else if(g[2] == 2)
{
q[p ++] = r; q[p ++] = u; q[p ++] = l; q[p ++] = d;
q[p ++] = r; q[p ++] = d; q[p ++] = l; q[p ++] = u;
q[p ++] = d; q[p ++] = l; q[p ++] = u; q[p ++] = r;
g[4] = g[1]; g[1] = g[5]; g[5] = g[8]; g[8] = g[7]; g[7] = g[6]; g[6] = g[3]; g[3] = g[2]; g[2] = g[4]; g[4] = 0;
}
else if(g[5] == 2)
{
q[p ++] = r; q[p ++] = d; q[p ++] = l; q[p ++] = u;
q[p ++] = d; q[p ++] = l; q[p ++] = u; q[p ++] = r;
g[4] = g[3]; g[3] = g[5]; g[5] = g[8]; g[8] = g[7]; g[7] = g[6]; g[6] = g[4]; g[4] = 0;
}
else if(g[6] == 2)
{
q[p ++] = l; q[p ++] = d; q[p ++] = r; q[p ++] = u;
g[4] = g[3]; g[3] = g[6]; g[6] = g[7]; g[7] = g[4]; g[4] = 0;
}
else if(g[7] == 2)
{
q[p ++] = d; q[p ++] = l; q[p ++] = u; q[p ++] = r;
g[4] = g[3]; g[3] = g[7]; g[7] = g[6]; g[6] = g[4]; g[4] = 0;
}
else if(g[8] == 2)
{
q[p ++] = d; q[p ++] = r; q[p ++] = u; q[p ++] = l;
q[p ++] = d; q[p ++] = l; q[p ++] = u; q[p ++] = r;
g[4] = g[3]; g[3] = g[8]; g[8] = g[5]; g[5] = g[7]; g[7] = g[6]; g[6] = g[4]; g[4] = 0;
}
//(4) 1 ready
if(g[6] == 1)
{
q[p ++] = d;
g[4] = g[7]; g[7] = 0;
for(i = 0; i < 5; i ++)
{
q[p ++] = l; q[p ++] = u; q[p ++] = u; q[p ++] = r; q[p ++] = r; q[p ++] = d; q[p ++] = d; q[p ++] = l;
}
g[7] = g[0]; g[0] = g[6]; g[6] = g[5]; g[5] = g[1]; g[1] = g[3]; g[3] = g[8]; g[8] = g[2]; g[2] = g[7]; g[7] = 0;
}
else
{
// 1 in the 5th place
if(g[1] == 1)
{
q[p ++] = u; q[p ++] = r; q[p ++] = d; q[p ++] = l;
g[4] = g[1]; g[1] = g[2]; g[2] = g[5]; g[5] = g[4]; g[4] = 0;
}
else if(g[2] == 1)
{
q[p ++] = r; q[p ++] = u; q[p ++] = l; q[p ++] = d;
g[4] = g[1]; g[1] = g[5]; g[5] = g[2]; g[2] = g[4]; g[4] = 0;
}
else if(g[7] == 1)
{
q[p ++] = d; q[p ++] = r; q[p ++] = u; q[p ++] = l;
g[4] = g[5]; g[5] = g[7]; g[7] = g[8]; g[8] = g[4]; g[4] = 0;
}
else if(g[8] == 1)
{
q[p ++] = r; q[p ++] = d; q[p ++] = l; q[p ++] = u;
g[4] = g[5]; g[5] = g[8]; g[8] = g[7]; g[7] = g[4]; g[4] = 0;
}
// other operations
q[p ++] = r;
g[4] = g[5]; g[5] = 0;
for(i = 0; i < 3; i ++)
{
q[p ++] = l; q[p ++] = l; q[p ++] = u; q[p ++] = r; q[p ++] = r; q[p ++] = d;
}
g[5] = g[0]; g[0] = g[4]; g[4] = g[1]; g[1] = g[3]; g[3] = g[2]; g[2] = g[5]; g[5] = 0;
q[p ++] = l; q[p ++] = d;
g[5] = g[4]; g[4] = g[7]; g[7] = 0;
}
//(5) 4 ready
if(g[3] == 4)
{
q[p ++] = u; q[p ++] = l; q[p ++] = d; q[p ++] = r;
q[p ++] = r; q[p ++] = u; q[p ++] = l; q[p ++] = d;
g[7] = g[3]; g[3] = g[6]; g[6] = g[4]; g[4] = g[8]; g[8] = g[5]; g[5] = g[7]; g[7] = 0;
}
else if(g[4] == 4)
{
q[p ++] = r; q[p ++] = u; q[p ++] = l; q[p ++] = d;
g[7] = g[4]; g[4] = g[8]; g[8] = g[5]; g[5] = g[7]; g[7] = 0;
}
else if(g[6] == 4)
{
q[p ++] = l; q[p ++] = u; q[p ++] = r; q[p ++] = d;
q[p ++] = r; q[p ++] = u; q[p ++] = l; q[p ++] = d;
g[7] = g[3]; g[3] = g[4]; g[4] = g[8]; g[8] = g[5]; g[5] = g[6]; g[6] = g[7]; g[7] = 0;
}
else if(g[8] == 4)
{
q[p ++] = u; q[p ++] = r; q[p ++] = d; q[p ++] = l;
g[7] = g[4]; g[4] = g[5]; g[5] = g[8]; g[8] = g[7]; g[7] = 0;
}
//(6) 5 ready
if(g[8] != 5)
{
if(g[3] == 5)
{
q[p ++] = l; q[p ++] = u; q[p ++] = r; q[p ++] = d;
g[7] = g[3]; g[3] = g[4]; g[4] = g[6]; g[6] = g[7]; g[7] = 0;
}
else if(g[4] == 5)
{
q[p ++] = u; q[p ++] = l; q[p ++] = d; q[p ++] = r;
g[7] = g[3]; g[3] = g[6]; g[6] = g[4]; g[4] = g[7]; g[7] = 0;
}
q[p ++] = r; q[p ++] = u; q[p ++] = l; q[p ++] = d;
g[7] = g[4]; g[4] = g[8]; g[8] = g[5]; g[5] = g[7]; g[7] = 0;
q[p ++] = r;
g[7] = g[8]; g[8] = 0;
q[p ++] = l; q[p ++] = l; q[p ++] = u; q[p ++] = r; q[p ++] = r; q[p ++] = d; q[p ++] = l;
g[8] = g[6]; g[6] = g[3]; g[3] = g[4]; g[4] = g[5]; g[5] = g[7]; g[7] = 0;
}
//(7) 6 ready
if(g[3] == 6)
{
q[p ++] = u; q[p ++] = l; q[p ++] = d; q[p ++] = r;
g[7] = g[3]; g[3] = g[6]; g[6] = g[4]; g[4] = g[7]; g[7] = 0;
}
else if(g[6] == 6)
{
q[p ++] = l; q[p ++] = u; q[p ++] = r; q[p ++] = d;
g[7] = g[3]; g[3] = g[4]; g[4] = g[6]; g[6] = g[7]; g[7] = 0;
}
q[p ++] = u;
g[7] = g[4]; g[4] = 0;
q[p ++] = r; q[p ++] = d; q[p ++] = l; q[p ++] = l; q[p ++] = u; q[p ++] = r; q[p ++] = r; q[p ++] = d;
g[4] = g[8]; g[8] = g[3]; g[3] = g[5]; g[5] = g[7]; g[7] = g[6]; g[6] = g[8]; g[8] = 0;
//(8) check
if(g[6] == 8)
printf("unsolvable\n");
else
{
q[p] = '\0';
printf("%s\n", q);
}
}
int main()
{
while(scanf("%s", b) == 1)
{
init();
solve();
}
return 0;
}