采用预处理的方法.因为结果状态只有一种,要判断某种状态到达结果状态的最少步数,如果直接做一个耗时,另一方面实现复杂.可以反向思考,我只要从结果状态搜索,每到一个状态,则该状态必然是合法状态,同时到达的步数也可以获得,并且只有一个起始状态只需搜索一边,即预处理一次即可.
接下来,就要根据题目条件分析状态的变化规则:
1.若0在中心,则可以和偶数位的数字进行交换;
2.若0在偶数位置,可以和前(-1),后(+1),以及中心位置的数字进行交换;
3.若0在奇数位置,可以和前(-1),后(+1)位置的数字进行交换.
最后,就是如何实现搜索了,开始我居然采用深度优先搜索,幸好数据规模小,没有死机,不过得出的结果让我迷茫了n久.反复想想,找个数据分析一下才发现,要找最少步数,当然要采用广度优先了,赶快修改......看来长时间不练习,最基本的东西都变得如此生疏了.........
Source:
#include<iostream>
#include<queue>
using namespace std;
void search();
struct Node
{
int v,i;
};
int res[6419760];//6543210-0123456=6419754
int cur[7]={0,1,2,3,4,5,6};
queue<Node> q;
int main()
{
int t,d;
Node nn;
memset(res,-1,6419760*sizeof(int));
res[0]=0;
nn.i=0;
nn.v=123456;
q.push(nn);
search();
//for(t=0;t<7;++t)cout<<cur[t]<<" ";
for(cin>>t;t>0;--t)
{
cin>>d;
cout<<res[d-123456]<<endl;
}
return 0;
}
void search()
{
int i,j,zi,k,s;
Node c;
while(!q.empty())
{
c=q.front();
q.pop();
for(i=6,zi=0;i>=0;--i)
{
cur[i]=c.v%10;
c.v/=10;
if(cur[i]==0)zi=i;
}
if(zi==0)
{
for(j=2;j<7;j+=2)
{
cur[zi]=cur[j];
cur[j]=0;
for(k=0,s=0;k<7;++k)s=s*10+cur[k];
if(res[s-123456]==-1)
{
// cout<<c.i+1<<"-------"<<s<<endl;
Node temp;
temp.v=s;
temp.i=c.i+1;
q.push(temp);
res[s-123456]=temp.i;
}
cur[j]=cur[zi];
cur[zi]=0;
}
}else if(zi%2==0)
{
//fore
j=zi-1;
cur[zi]=cur[j];
cur[j]=0;
for(k=0,s=0;k<7;++k)s=s*10+cur[k];
if(res[s-123456]==-1)
{
// cout<<c.i+1<<"-------"<<s<<endl;
Node temp;
temp.v=s;
temp.i=c.i+1;
q.push(temp);
res[s-123456]=temp.i;
}
cur[j]=cur[zi];
cur[zi]=0;
//back
if(zi+1==7)j=1;
else j=zi+1;
cur[zi]=cur[j];
cur[j]=0;
for(k=0,s=0;k<7;++k)s=s*10+cur[k];
if(res[s-123456]==-1)
{
// cout<<c.i+1<<"-------"<<s<<endl;
Node temp;
temp.v=s;
temp.i=c.i+1;
q.push(temp);
res[s-123456]=temp.i;
}
cur[j]=cur[zi];
cur[zi]=0;
//center
j=0;
cur[zi]=cur[j];
cur[j]=0;
for(k=0,s=0;k<7;++k)s=s*10+cur[k];
if(res[s-123456]==-1)
{
// cout<<c.i+1<<"-------"<<s<<endl;
Node temp;
temp.v=s;
temp.i=c.i+1;
q.push(temp);
res[s-123456]=temp.i;
}
cur[j]=cur[zi];