题目一：
总共七个格子，最左边有三颗棋子。用跳棋的规则，最少的步骤使得三个棋子走到七个格子的最右边。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
int a[8]; //保存信息，比如112保存为1110000
int visi[1002]; //看某个状态有没有被访问
int next[1002]; //记录所存的状态信息
int res[1002];
int con(int t1,int t2,int t3)
{
int ans=0;
ans+=pow(2,7-t1);
ans+=pow(2,7-t2);
ans+=pow(2,7-t3);
return ans;
}
void bfs(int sta)
{
queue<int> mq;
mq.push(sta);
int cur,i;
int t1,t2,t3;
while(!mq.empty())
{
cur=mq.front();
int pc=cur;
mq.pop();
if(cur==7) //终状态为0000111
{
break;
}
for(i=7;i>=1;i--) //再解压状态信息
{
a[i]=cur%2;
cur=cur/2;
}
cur=pc;
//先找到三个球的位置
for(i=1;i<=7;i++)
{
if(a[i])
{
t1=i;
i++;
break;
}
}
for(;i<=7;i++)
{
if(a[i])
{
t2=i;
i++;
break;
}
}
for(;i<=7;i++)
{
if(a[i])
{
t3=i;
i++;
break;
}
}
//cout<<t1<<" "<<t2<<" "<<t3<<endl;
//现在就是最麻烦的枚举状态的时候了
//我们假使三种情况，动t1,t2,t3如果能动的话，每次都动最远
int tmp;
//先动第一个
if(t2>t1+1) //中间有空格
{
tmp=con(t1+1,t2,t3);
if(!visi[tmp]) //如果此状态没访问过
{
visi[tmp]=1;
next[tmp]=cur; //记录状态转移过程
mq.push(tmp); //把状态加入队列中
}
}
else if((t2==t1+1&&t3>t2+2)||(t2==t1+1&&t3==t2+2&&t3==7))
{
tmp=con(t2,t2+1,t3);
if(!visi[tmp]) //如果此状态没访问过
{
visi[tmp]=1;
next[tmp]=cur; //记录状态转移过程
mq.push(tmp); //把状态加入队列中
}
}
else if(t2==t1+1&&t3==t2+2&&t3<7)
{
tmp=con(t2,t3,t3+1);
if(!visi[tmp]) //如果此状态没访问过
{
visi[tmp]=1;
next[tmp]=cur; //记录状态转移过程
mq.push(tmp); //把状态加入队列中
}
}
else if(t2==t1+1&&t3==t2+1)
{
//动不了第一个棋
}
//再试着动第二个
if(t3>t2+1) //t2后面有空格
{
tmp=con(t1,t2+1,t3);
if(!visi[tmp]) //如果此状态没访问过
{
visi[tmp]=1;
next[tmp]=cur; //记录状态转移过程
mq.push(tmp); //把状态加入队列中
}
}
else if(t3==t2+1&&t3==7)
{
//动不了第二个棋
}
else if(t3==t2+1&&t3<7)
{
tmp=con(t1,t3,t3+1);
if(!visi[tmp]) //如果此状态没访问过
{
visi[tmp]=1;
next[tmp]=cur; //记录状态转移过程
mq.push(tmp); //把状态加入队列中
}
}
//再试着动第三个
if(t3<7)
{
tmp=con(t1,t2,t3+1);
if(!visi[tmp]) //如果此状态没访问过
{
visi[tmp]=1;
next[tmp]=cur; //记录状态转移过程
mq.push(tmp); //把状态加入队列中
}
}
else if(t3==7)
{
//动不了第三个棋
}
//break;
}
}
int main()
{
int i,sta=0,j;
for(i=1;i<=3;i++)
{
a[i]=1;
sta+=pow(2,7-i);
}
for(i=4;i<=7;i++)
{
a[i]=0;
}
//cout<<sta<<endl;
//初始状态为1110000 初始值为112
memset(visi,0,sizeof(visi)); //把visi数组全部置为0都没访问过
bfs(sta);
int tt=0,tmp;
tmp=7;
while(tmp!=112)
{
res[tt++]=tmp;
//cout<<tmp<<endl;
tmp=next[tmp];
}
res[tt++]=tmp;
/*for(i=tt-1;i>=0;i--)
cout<<res[i]<<" ";
cout<<endl;*/
/*cout<<next[7]<<endl;
cout<<next[11]<<endl;
cout<<next[26]<<endl;
cout<<next[28]<<endl;
cout<<next[44]<<endl;
cout<<next[104]<<endl;*/
for(i=tt-1;i>=0;i--)
{
int qq=res[i];
for(j=7;j>=1;j--)
{
a[j]=qq%2;
qq=qq/2;
}
for(j=1;j<=7;j++)
cout<<a[j];
cout<<endl;
}
return 0;
}
运行结果：
题目二：
总共七个格子，最左边有三颗白棋，最右边有三颗黑棋。用跳棋的规则，最少的步骤使得三个白棋走到最右边，三个黑棋走到最左边。
还有一个规则，自己只能通过自己的棋子作为炮台跳。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<cstdlib>
using namespace std;
int a[8]; //保存信息，比如112保存为1110000
int b[8];
int visi[2500]; //看某个状态有没有被访问
int next[2500]; //记录所存的状态信息
int res[2500];
void output()
{
for(int i=1;i<=7;i++)
cout<<a[i]<<" ";
cout<<endl;
}
int con()
{
int i;
int ans=0;
for(i=1; i<=7; i++)
ans+=b[i]*pow(3,7-i);
return ans;
}
void mcpy()
{
int i;
for(i=1; i<=7; i++)
b[i]=a[i];
}
void bfs(int sta)
{
int mq[2500];
int ps=0,pen=1;
//pstart pend
mq[ps]=sta;
int cur,i;
int t;
while(ps<pen) //队列中还有值
{
cur=mq[ps];
int pc=cur;
ps++;
if(cur==2119) //终状态为2220111
{
//cout<<"dsdsd"<<endl;
break;
}
for(i=7; i>=1; i--) //再解压状态信息
{
a[i]=cur%3;
cur=cur/3;
}
cur=pc;
for(i=1; i<=7; i++)
{
if(a[i]==0)
{
t=i; //记录空格的位置
break;
}
}
if(t+1<=7&&a[t+1]==2) //黑棋左移1
{
mcpy();
b[t]=2,b[t+1]=0;
int tmp=con();
if(!visi[tmp])
{
visi[tmp]=1;
next[tmp]=cur;
mq[pen++]=tmp;
}
}
else if(t+2<=7&&a[t+1]==1&&a[t+2]==2) //黑棋左移2
{
mcpy();
b[t]=2,b[t+2]=0;
int tmp=con();
if(!visi[tmp])
{
visi[tmp]=1;
next[tmp]=cur;
mq[pen++]=tmp;
}
}
if(t-1>=1&&a[t-1]==1) //白棋右移1
{
mcpy();
b[t]=1,b[t-1]=0;
int tmp=con();
if(!visi[tmp])
{
visi[tmp]=1;
next[tmp]=cur;
mq[pen++]=tmp;
}
}
else if(t-2>=1&&a[t-1]==2&&a[t-2]==1) //白棋右移2
{
mcpy();
b[t]=1,b[t-2]=0;
int tmp=con();
if(!visi[tmp])
{
visi[tmp]=1;
next[tmp]=cur;
mq[pen++]=tmp;
}
}
}
}
int main()
{
int i,sta=0,j;
for(i=1; i<=3; i++)
{
a[i]=1;
sta+=a[i]*pow(3,7-i);
}
for(i=4; i<=4; i++)
{
a[i]=0;
}
for(i=5; i<=7; i++)
{
a[i]=2;
sta+=a[i]*pow(3,7-i);
}
//cout<<sta<<endl;
//初始状态为1110222 初始值为1079
memset(visi,0,sizeof(visi)); //把visi数组全部置为0都没访问过
cout<<sta<<endl;
bfs(sta);
int tt=0,tmp;
tmp=2119;
while(tmp!=1079)
{
res[tt++]=tmp;
tmp=next[tmp];
}
res[tt++]=tmp;
cout<<"总共需要: "<<tt-1<<"步."<<endl;
for(i=tt-1;i>=0;i--)
{
int qq=res[i];
for(j=7;j>=1;j--)
{
a[j]=qq%3;
qq=qq/3;
}
for(j=1;j<=7;j++)
cout<<a[j];
cout<<endl;
}
return 0;
}
运行结果：
原文：http://blog.csdn.net/coraline_m/article/details/19625567
