BFS 八数码的变形 XTU 1156 Game(二)
swap(mid[3],mid[4]);
q.sp=temp.sp+1;
q.pos=4;
q.ss=mid;
if(mp.find(mid)==mp.end())
que.push(q);
}
else if(temp.pos==4)
{
mid=temp.ss;
swap(mid[4],mid[3]);
q.sp=temp.sp+1;
q.pos=3;
q.ss=mid;
if(mp.find(mid)==mp.end())
que.push(q);
mid=temp.ss;
swap(mid[4],mid[5]);
q.sp=temp.sp+1;
q.pos=5;
q.ss=mid;
if(mp.find(mid)==mp.end())
que.push(q);
mid=temp.ss;
swap(mid[4],mid[1]);
q.sp=temp.sp+1;
q.pos=1;
q.ss=mid;
if(mp.find(mid)==mp.end())
que.push(q);
}
else if(temp.pos==5)
{
mid=temp.ss;
swap(mid[5],mid[2]);
q.sp=temp.sp+1;
q.pos=2;
q.ss=mid;
if(mp.find(mid)==mp.end())
que.push(q);
mid=temp.ss;
swap(mid[5],mid[4]);
q.sp=temp.sp+1;
q.pos=4;
q.ss=mid;
if(mp.find(mid)==mp.end())
que.push(q);
}
}
}
int main()
{
int cas,i,j,kk1=0,kk2=0,sx,sy;
while(scanf("%d",&cas)!=EOF)
{
while(cas--)
{
s="\0";ans="\0";//注意 string的清空可以用这个方法
mp.clear();
step=999999999;
for(i=0;i<6;i++)
{
scanf("%d",&a[i]);
s+=(a[i]+'0');
}
int k,kk=0;
for(i=0;i<2;i++)
for(j=0;j<3;j++)
{
scanf("%d",&mmap[i][j]);
b[kk++]=mmap[i][j];
ans+=(mmap[i][j]+'0');
if(mmap[i][j]==0)
{
k=i*3+j;//0在字符串中对应的位置
}
}
ans.swap(s);//由于上面的 k我求反了 求成终态的0的位置了 所以我交换一下终态和始态 哪个做终始都一样
int n1=0,n2=0;
for(i=0;i<6;i++)
{
for(j=i+1;j<6;j++)
{ www.2cto.com
if(a[i]>a[j]&&a[i]!=0&&a[j]!=0) n1++;
if(b[i]>b[j]&&b[i]!=0&&b[j]!=0) n2++;
}
}
if(n1%2!=n2%2) {printf("Impossible!\n");continue;}
BFS(k,0);
if(step!=999999999)
printf("%d\n",step);
else printf("Impossible!\n");
}
}
return 0;
}