BFS 8数码的变形 XTU 1156 Game

BFS 八数码的变形 XTU 1156 Game
GameAccepted : 21 Submit : 106Time Limit : 1000 MS Memory Limit : 65536 KB
题目描述

小茹今年生日收到了小思送的一份奇特的礼物。礼物是一个2*3个格子的棋盘，上面有5个数字方块1~5。每次可以把空格子边上的一个数字方块到移动到空余的格子，方块不能移出棋盘。小思要求小茹把它移动到特定的样子，然后可以满足小茹的一个愿望。小茹想度过一个快乐的生日，而不是费脑筋的移动方块，于是她向你求助。请你帮小茹求出移动的最少次数，如果永远不可能达到，输出 "Impossible!"

第一行为数字n，代表有n组样例。每组样例有4行非负整数，空格用数字0代替。第1行和第2行为礼物的起始状态，第3、4行目标状态。

对于每组样例,输出最少的移动次数，如果不能达到输出"Impossible!"。

20 1 23 4 51 2 03 4 51 2 34 5 01 2 34 0 5

21

XTUCPC2013

http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1156

/*思路：把矩形抽象为一个字符串  记录状态 看是否走过   然后用BFS搜索  我一开始用DFS 怎么优化都是超时 这种题目  有个优化  就是初始状态和终止状态的逆序数相同  如果不同则无解    加上这个优化 可以提快好几倍的速度*/#include<stdio.h>#include<string.h>#include<string>#include<map>#include<iostream>#include <algorithm>#include<queue>using namespace std;int a[6],b[6],mmap[2][3];string ans,s;map<string,int>mp;map<string,int>::iterator  it;int step;struct haha{int pos;//0的位置string ss;//矩阵对应的字符串int sp;//step 走的步数}temp,q;void BFS(int k,int sp){int i;queue<struct haha>que;q.sp=sp;q.ss=s;q.pos=k;que.push(q);while(!que.empty()){string mid;temp=que.front();que.pop();if(temp.ss==ans) {step=temp.sp;return;}mp[temp.ss]=1;if(temp.pos==0)//0可以走的方向{mid=temp.ss;swap(mid[0],mid[1]);q.sp=temp.sp+1;q.pos=1;q.ss=mid;if(mp.find(mid)==mp.end()) que.push(q);mid=temp.ss;swap(mid[0],mid[3]);q.sp=temp.sp+1;q.pos=3;q.ss=mid;if(mp.find(mid)==mp.end()) que.push(q);}else if(temp.pos==1){mid=temp.ss;swap(mid[1],mid[0]);q.sp=temp.sp+1;q.pos=0;q.ss=mid;if(mp.find(mid)==mp.end()) que.push(q);mid=temp.ss;swap(mid[1],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[1],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==2){mid=temp.ss;swap(mid[2],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[2],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==3){      mid=temp.ss;  swap(mid[3],mid[0]);  q.sp=temp.sp+1;  q.pos=0;  q.ss=mid;  if(mp.find(mid)==mp.end())   que.push(q);    mid=temp.ss;  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++){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;}