学习了多位大牛的方法，看看到底能把时耗降到多少？
A*
// zojfulltest: 30000ms
# include <stdio.h>
# include <ctype.h>
# include <stdlib.h>
# include <string.h> # define DATA(x,i) (((x)>>((i)*))&0x7)
# define ZERO(x) ((x)>>)
# define F(x) ((x)&0xFF)
# define D(x) (((x)>>)&0xF)
# define P(x) ((x)>>)
# define MAKE(f,d,p) ((f)|((d)<<)|((p)<<))
# define LESS(x,y) (((x)-(y))>>)
# define SWP(i,j,t) (((t)<<(*(i)))-((t)<<(*(j)))+((j)<<)-((i)<<)) const unsigned int maxd = ;
//dest: 0100 0000 0001 1111 0101 1000 1101 0001
const unsigned int dest = 0x401F58D1;
const unsigned int hashmod = ;
const unsigned int maxnode = 0x1<<;
const unsigned int maxsize = 0x1<<;
const int mv[][] = {{-,-,, },{-,,, },{-,,-, },
{ ,-,, },{ ,,, },{ ,,-, },
{ ,-,,-},{ ,,,-},{ ,,-,-}};
const char mvs[] = "ulrd"; struct state {
unsigned int u, v;
};
state a[maxnode], child;
unsigned int src, depth, totnode, h[][], t[];
unsigned int head[hashmod], next[maxnode];
unsigned int hp[maxsize], hps;
unsigned int stk[maxsize], top; void init(void)
{
memset(h, , sizeof(h));
for (int j, i = ; i != ; ++i) {
for (j = ; j != ; ++j) {
h[i][j] = abs(j/-(i-)/)+abs(j%-(i-)%);
}
}
for (int i = ; i != ; ++i) {
h[][i] = h[][i];
}
}
bool read_src(void)
{
src = ;
for (int ch, i = ; i != ; ) {
ch = getchar();
if (isdigit(ch)) t[i++] = ch-'';
else if (ch == 'x') {
t[i] = ;
src |= ((i++)<<);
} else if (ch == EOF) return false;
}
for (int i = ; i != ; ++i) src |= ((t[i]&0x7)<<(*i));
return true;
}
bool no_answer(void)
{
int inv = -ZERO(src), i, j;
for (i = ; i != ; ++i) {
for (j = i+; j != ; ++j) {
inv += LESS(t[j],t[i]);
}
}
return ((inv)&0x1);
}
void print_sol(int ID)
{
if (ID == ) return ;
print_sol(P(a[ID].v));
putchar( mvs[D(a[ID].v)] );
}
void addnode(void)
{
int k = child.u % hashmod;
for (int w = head[k]; w ; w = next[w]) {
if (a[w].u == child.u) {
if ( LESS(F(child.v), F(a[w].v)) ) {
a[w].v = child.v;
stk[top++] = w;
}
return ;
}
}
a[++totnode] = child;
next[totnode] = head[k]; head[k] = totnode;
if ( F(child.v) == depth ) stk[top++] = totnode;
else hp[hps++] = totnode;
} void solve(void)
{
if (no_answer()) { puts("unsolvable"); return; }
if (src == dest) { puts(""); return ; }
depth = -h[][ZERO(src)];
totnode = ;
hps = top = ;
memset(head, , sizeof(head));
for (int i = ; i != ; ++i) {
depth += h[ DATA(src,i) ][i];
}
child.u = src;
child.v = MAKE(depth, , );
addnode();
unsigned int ID;
for ( ; LESS(depth, maxd); depth += ) {
while (hps) {
ID = hp[--hps];
if ( F(a[ID].v) == depth ) {
stk[top++] = ID;
}
}
while (top) {
ID = stk[--top];
state & cur = a[ID];
int i = ZERO(cur.u), j;
for (int r = ; r != ; ++r) {
if (-!=(j=mv[i][r]) && (D(cur.v)+r)!=) {
int t = DATA(cur.u, j);
child.u = cur.u+SWP(i,j,t);
int f = F(cur.v)++h[t][i]-h[t][j];
child.v = MAKE(f,r,ID);
if (child.u == dest) {
a[++totnode] = child;
print_sol(totnode); puts("");
return ;
}
addnode();
}
}
}
}
} int main()
{
init();
while (read_src()) solve(); return ;
}
BFS + 记忆化
// zojfulltest: 1012ms
# include <stdio.h>
# include <ctype.h>
# include <string.h> # define LESS(x,y) (((x)-(y))>>)
# define DATA(x,i) (((x)>>((i)*))&0x7)
# define ZERO(x) ((x)>>)
# define P(x) ((x)>>)
# define D(x) ((x)&0xF)
# define MAKE(d,p) ((d)|((p)<<))
# define SWP(i,j,t) (((t)<<(*(i)))-((t)<<(*(j)))+((j)<<)-((i)<<)) const int totnode = ;
const int maxsize = ;
const int dest = 0x401F58D1;
const int destID = ;
const int fact[] = {,,,,,,,,};
const int mv[][] = {{-,-,, },{-,,, },{-,,-, },
{ ,-,, },{ ,,, },{ ,,-, },
{ ,-,,-},{ ,,,-},{ ,,-,-}};
const char mvs[] = "ulrd"; struct state {
unsigned int s;
unsigned int c;
} hp[maxsize], child; unsigned int front, rear, src, table[totnode]; unsigned int cantor(unsigned int s)
{
unsigned int ret = ;
unsigned int t[], i;
for (i = ; i != ; ++i) t[i] = DATA(s,i);
for (i = ; DATA(s,i)||i==ZERO(s); ++i) ;
t[i] = ;
for (i = ; i != ; ++i) {
unsigned int inv = ;
for (int j = ; j != i; ++j) {
inv += LESS(t[j],t[i]);
}
ret += inv*fact[i];
}
return ret;
}
void build_tree(void)
{
front = rear = ;
child.s = dest, child.c = destID;
table[destID] = MAKE(,destID);
hp[rear++] = child;
while (LESS(front, rear)) {
state & cur = hp[front++];
int i = ZERO(cur.s), d = table[cur.c], j;
for (int r = ; r != ; ++r) {
if (~(j=mv[i][r]) && (d+r)!=) {
child.s = cur.s+SWP(i,j,DATA(cur.s,j));
child.c = cantor(child.s);
if (table[child.c] == ) {
table[child.c] = MAKE(r, cur.c);
hp[rear++] = child;
}
}
}
}
}
bool read_src(void)
{
src = ;
for (int ch, i = ; i != ; ) {
ch = getchar();
if (isdigit(ch)) src |= (((ch-'')&0x7)<<(*i++));
else if (ch == 'x') src |= ((i++)<<);
else if (ch == EOF) return false;
}
return true;
}
void print_sol(int ID)
{
while (ID != destID) {
putchar(mvs[-D(table[ID])]);
ID = P(table[ID]);
}
}
void solve(void)
{
unsigned int c = cantor(src);
if (!table[c]) printf("unsolvable");
else print_sol(c);
printf("\n");
}
int main()
{
build_tree();
while (read_src()) solve();
}
构造
# include <stdio.h>
# include <ctype.h>
# include <string.h> # define LESS(x, y) (((x)-(y))>>)
# define REP(n) for ((i) = ; src[i] != (n); ++(i)) const char *t0[] = {"rd","d","ld","r","","l","ur","u","ul"};
const char *t1[] = {"","lurd","urdllurd","uldr","","urdlurdllurd","ldruuldr","ldruldruuldr","rdluurdlurdllurd"};
const char *t2[] = {"","urddllur","urdlurddllur","","","rdllur","ldru","dlur","druldlur"};
const char *t3[] = {"","ruld","","","","urdl","dlurdrulurdlldru","drulurdl","rdluurdl"};
const char *t4 = "ldrrulurdl";
const char *t5[] = {"","","","","","rdllur","ldru","dlur","druldlur"};
const char *t6[] = {"","","","","","rdlu","dlurdrulldrurdlu","","rdlurdlu"};
const char *t7 = "dlur";
const char *t8[] = {"","","","","","rd","","dr","rdlurd"};
const char *mvs = "ulrd";
const int mv[][] = {{-,-,, },{-,,, },{-,,-, },
{ ,-,, },{ ,,, },{ ,,-, },
{ ,-,,-},{ ,,,-},{ ,,-,-}
}; unsigned int src[], pos;
char ans[], top; int mr(char ch)
{
switch(ch) {
case 'u':
return ;
case 'l':
return ;
case 'r':
return ;
case 'd':
return ;
}
}
void mov(const char * str)
{
int n = strlen(str);
for (int i = ; i < n; ++i) {
int t = mv[pos][mr(str[i])];
src[pos] = src[t];
src[pos = t] = ;
}
memcpy(ans+top, str, n);
top += n;
}
void solve(void)
{
int i;
top = ;
mov( t0[pos] ); // 0->4
REP();
mov( t1[i] ); // 1->0
REP();
mov( t2[i] ); // 3->3
REP();
mov( t3[i] ); // 2->2
mov( t4 ); // 2->1, 3->2
REP();
mov( t5[i] ); // 7->3
REP();
mov( t6[i] ); // 4->7
mov( t7 ); // 4->3, 7->7
REP();
mov( t8[i] ); // 5->4, 0->8
ans[top] = ;
if ( src[] == ) puts(ans);
}
bool no_answer(void)
{
int inv = -pos;
for (int i = ; i != ; ++i) {
for (int j = i+; j != ; ++j) {
inv += LESS(src[j], src[i]);
}
}
return ((inv)&0x1);
}
bool read_src(void)
{
for (int i = ; i != ; ) {
int ch = getchar();
if (isdigit(ch)) src[i++] = ch-'';
else if (ch == 'x') src[pos = i++] = ;
else if (ch == EOF) return false;
}
return true;
}
int main()
{
while ( read_src() ) {
if ( no_answer() ) puts("unsolvable");
else solve();
}
return ;
}