BFS:
#include <iostream>
using namespace std
int fac[10]={1,1}
bool tflag[9]
struct bbit{
unsigned int val:4
}
struct bbbit
{
unsigned int val:2
}
struct Node
{
bbit s[9],pos
int step
bbbit path[21],tag
int hashval()
{
int ret=0,i,j,tmp
memset(tflag,false,sizeof(tflag))
for(i=0i<8i++)
{
tmp=0
for(j=0j<s[i].valj++)
if(!tflag[j])
tmp++
ret+=tmp*fac[8-i]
tflag[s[i].val]=true
}
return ret
}
bool up()
{
if(pos.val<=2)return false
s[pos.val].val^=s[pos.val-3].val
s[pos.val-3].val^=s[pos.val].val
s[pos.val].val^=s[pos.val-3].val
path[step].val=0
pos.val-=3
return true
}
bool down()
{
if(pos.val>=6)return false
s[pos.val].val^=s[pos.val+3].val
s[pos.val+3].val^=s[pos.val].val
s[pos.val].val^=s[pos.val+3].val
path[step].val=1
pos.val+=3
return true
}
bool left()
{
if(pos.val==0||pos.val==3||pos.val==6)return false
s[pos.val].val^=s[pos.val-1].val
s[pos.val-1].val^=s[pos.val].val
s[pos.val].val^=s[pos.val-1].val
path[step].val=2
pos.val--
return true
}
bool right()
{
if(pos.val==2||pos.val==5||pos.val==8)return false
s[pos.val].val^=s[pos.val+1].val
s[pos.val+1].val^=s[pos.val].val
s[pos.val].val^=s[pos.val+1].val
path[step].val=3
pos.val++
return true
}
bool operator==(const Node&x)const
{
int i
for(i=0i<9i++)if(s[i].val!=x.s[i].val)return false
return true
}
}Q[362880],S,A,tmp,top
struct Hash
{
bool d1,d2
Node D
}hash[362880]
inline void mkfac(){int ifor(i=2i<=9i++)fac[i]=fac[i-1]*i}
inline int eval(char c){return c=='x'?0:c-'0'}
void o(Node x,Node y)
{
int i
for(i=1i<=x.stepi++)
{
switch(x.path[i].val)
{
case 0:putchar('u')break
case 1:putchar('d')break
case 2:putchar('l')break
case 3:putchar('r')break
}
}
for(i=y.stepi>=1i--)
switch(y.path[i].val){
case 0:putchar('d')break
case 1:putchar('u')break
case 2:putchar('r')break
case 3:putchar('l')break
}
puts("")
}
int main()
{
char buf[11]
int i,t,l,r
bool flag
mkfac()
while(NULL!=gets(buf))
{
t=0
for(i=0i<=7i++)A.s[i].val=i+1A.s[8].val=0A.pos.val=8
for(i=0buf[i]i++)
{
if(buf[i]==' ')continue
S.s[t].val=eval(buf[i])
if(S.s[t].val==0)
S.pos.val=t
t++
}
l=r=0
flag=false
for(i=0i<362880i++)hash[i].d1=hash[i].d2=false
S.step=0S.tag.val=1
A.step=0A.tag.val=2
Q[r++]=S//tag.val:1
Q[r++]=A//tag.val:2
while(l<=r)
{
top=Q[l++]
top.step++
tmp=top
if(tmp.up())
{
if(tmp.tag.val==1)
{
if(!hash[t=tmp.hashval()].d1)
{
hash[t].d1=true
Q[r++]=tmp
if(hash[t].d2&&hash[t].D==tmp)
{
//find ans...
o(tmp,hash[t].D)
goto AA
}
if(!hash[t].d2)hash[t].D=tmp
}
}
else
{
if(!hash[t=tmp.hashval()].d2)
{
hash[t].d2=true
Q[r++]=tmp
if(hash[t].d1&&hash[t].D==tmp)
{
//find ans...
o(hash[t].D,tmp)
goto AA
}
if(!hash[t].d1)hash[t].D=tmp
}
}
}
tmp=top
if(tmp.down())
{
if(tmp.tag.val==1)
{
if(!hash[t=tmp.hashval()].d1)
{
hash[t].d1=true
Q[r++]=tmp
if(hash[t].d2&&hash[t].D==tmp)
{
//find ans...
o(tmp,hash[t].D)
goto AA
}
if(!hash[t].d2)hash[t].D=tmp
}
}
else
{
if(!hash[t=tmp.hashval()].d2)
{
hash[t].d2=true
Q[r++]=tmp
if(hash[t].d1&&hash[t].D==tmp)
{
//find ans...
o(hash[t].D,tmp)
goto AA
}
if(!hash[t].d1)hash[t].D=tmp
}
}
}
tmp=top
if(tmp.left())
{
if(tmp.tag.val==1)
{
if(!hash[t=tmp.hashval()].d1)
{
hash[t].d1=true
Q[r++]=tmp
if(hash[t].d2&&hash[t].D==tmp)
{
//find ans...
o(tmp,hash[t].D)
goto AA
}
if(!hash[t].d2)hash[t].D=tmp
}
}
else
{
if(!hash[t=tmp.hashval()].d2)
{
hash[t].d2=true
Q[r++]=tmp
if(hash[t].d1&&hash[t].D==tmp)
{
//find ans...
o(hash[t].D,tmp)
goto AA
}
if(!hash[t].d1)hash[t].D=tmp
}
}
}
tmp=top
if(tmp.right())
{
if(tmp.tag.val==1)
{
if(!hash[t=tmp.hashval()].d1)
{
hash[t].d1=true
Q[r++]=tmp
if(hash[t].d2&&hash[t].D==tmp)
{
//find ans...
o(tmp,hash[t].D)
goto AA
}
if(!hash[t].d2)hash[t].D=tmp
}
}
else
{
if(!hash[t=tmp.hashval()].d2)
{
hash[t].d2=true
Q[r++]=tmp
if(hash[t].d1&&hash[t].D==tmp)
{
//find ans...
o(hash[t].D,tmp)
goto AA
}
if(!hash[t].d1)hash[t].D=tmp
}
}
}
}
AA:flag=true
if(!flag)
puts("unsolvable")
}
return 0
}
A*:
#include <iostream>
#include <queue>
using namespace std
int fac[10]={1,1}
struct Node
{
int s[9],step,pos
char path[501]
int hashval()
{
int ret=0,i,j,tmp
bool flag[9]
memset(flag,false,sizeof(flag))
for(i=0i<8i++)
{
tmp=0
for(j=0j<s[i]j++)
if(!flag[j])
tmp++
ret+=tmp*fac[8-i]
flag[s[i]]=true
}
return ret
}
bool up()
{
if(pos<=2)return false
s[pos]^=s[pos-3]
s[pos-3]^=s[pos]
s[pos]^=s[pos-3]
path[step]='u'
pos-=3
return true
}
bool down()
{
if(pos>=6)return false
s[pos]^=s[pos+3]
s[pos+3]^=s[pos]
s[pos]^=s[pos+3]
path[step]='d'
pos+=3
return true
}
bool left()
{
if(pos==0||pos==3||pos==6)return false
s[pos]^=s[pos-1]
s[pos-1]^=s[pos]
s[pos]^=s[pos-1]
path[step]='l'
pos--
return true
}
bool right()
{
if(pos==2||pos==5||pos==8)return false
s[pos]^=s[pos+1]
s[pos+1]^=s[pos]
s[pos]^=s[pos+1]
path[step]='r'
pos++
return true
}
bool operator==(const Node&x)const
{
int i
for(i=0i<9i++)if(s[i]!=x.s[i])return false
return true
}
void show()
{
int i,j
for(i=0i<=6i+=3,cout<<endl)
for(j=ij<=i+2j++)
cout<<s[j]
}
bool operator<(const Node&x)const
{
int la=0,lb=0,i
for(i=0i<8i++)if(s[i]!=i+1)la++la+=(s[8]!=0)
for(i=0i<8i++)if(x.s[i]!=i+1)lb++lb+=(x.s[8]!=0)
return la>lb
}
}S,A,tmp,top
priority_queue<Node>Q
bool hash[362880]
void mkfac(){int ifor(i=2i<=9i++)fac[i]=fac[i-1]*i}
int eval(char c){return c=='x'?0:c-'0'}
void output(Node x)
{
int i
for(i=1i<=x.stepi++)
putchar(x.path[i])
puts("")
}
int main()
{
char buf[11]
int i,t,l,r
bool flag
mkfac()
while(NULL!=gets(buf))
{
t=0
for(i=0i<=7i++)A.s[i]=i+1A.s[8]=0A.pos=8
for(i=0buf[i]i++)
{
if(buf[i]==' ')continue
S.s[t]=eval(buf[i])
if(S.s[t]==0)
S.pos=t
t++
}
l=r=0
flag=false
memset(hash,false,sizeof(hash))
S.step=0
while(!Q.empty())Q.pop()
Q.push(S)
while(!Q.empty())
{
top=Q.top()
Q.pop()
top.step++
tmp=top
if(tmp.up())
{
if(!hash[t=tmp.hashval()])
{
hash[t]=true
Q.push(tmp)
if(tmp==A)
{
//find ans...
output(tmp)
goto AA
}
}
}
tmp=top
if(tmp.down())
{
if(!hash[t=tmp.hashval()])
{
hash[t]=true
Q.push(tmp)
if(tmp==A)
{
//find ans...
output(tmp)
goto AA
}
}
}
tmp=top
if(tmp.left())
{
if(!hash[t=tmp.hashval()])
{
hash[t]=true
Q.push(tmp)
if(tmp==A)
{
//find ans...
output(tmp)
goto AA
}
}
}
tmp=top
if(tmp.right())
{
if(!hash[t=tmp.hashval()])
{
hash[t]=true
Q.push(tmp)
if(tmp==A)
{
//find ans...
output(tmp)
goto AA
}
}
}
}
AA:flag=true
if(!flag)
puts("unsolvable")
}
return 0
}
基于51的程序：#include <reg52.h>
sbit sda=P0^5
sbit scl=P0^6
code char led_code[19]={0x11,0xd7,0x32,0x92,0xd4, // 0,1,2,3,4
0x98,0x18,0xd3,0x10,0x90, // 5,6,7,8,9
0x50,0x1c,0x39,0x16,0x38, // a,b,c,d,e,
0x78,0xfe,0xef,0xff} // f - dot dark
void seperate(unsigned char second,minute,hour) //1调用拆分函数
void display(unsigned char second,minute,hour) // 2调用显示函数 一定要在各处强调unsignde吗？
void shift(unsigned char) //3调用移位函数
void delay_1s(unsigned int x) //4调用延时函数
unsigned char second,minute,hour
unsigned char second0,second1,
minute0,minute1,
hour0,hour1// 这三行表示了时、分、秒所占数码管的个数和位置。 叫形参？
void main()
{
while(1)
{
for(hour=0hour<24hour++) //三个for语句的安排妙啊！ 我们看到的钟表时分秒的变化
！
{
for(minute=0minute<60minute++)
{
for(second=0second<60second++)
{
display(second,minute,hour)
delay_1s(65535)
}
}
}
}
}
void display(unsigned char second,minute,hour) //2对显示函数的说明
{
seperate(second,minute,hour)
shift(second0)
shift(second1)
shift(16)
shift(minute0)
shift(minute1)
shift(16)
shift(hour0)
shift(hour1)
}
void seperate(unsigned char second,minute,hour)//1对拆分函数的说明
{
second0=second%10
second1=second/10
minute0=minute%10
minute1=minute/10
hour0=hour%10
hour1=hour/10
}
void shift(unsigned char n) //3对移位函数的说明
{
unsigned char dat,minute
dat=led_code[n]
scl=0
for(minute=0minute<8minute++)
{
if (dat&0x80) sda=1
else sda=0
scl=1
scl=0
dat<<=1
}
}
void delay_1s(unsigned int a) //4对延时函数的说明
{
while(a--)
}
