Game Accepted : 21 Submit : 106 Time Limit : 1000 MS Memory Limit : 65536 KB 題目描述 小茹今年生日收到了小思送的一份奇特的禮物。禮物是一個2*3個格子的棋盤，上面有5個數字方塊1~5。每次可以把空格子邊上的一個數字方塊到移動到空余的格子，方塊不能移出棋盤。小思要求小茹把它移動到特定的樣子，然後可以滿足小茹的一個願望。小茹想度過一個快樂的生日，而不是費腦筋的移動方塊，於是她向你求助。請你幫小茹求出移動的最少次數，如果永遠不可能達到，輸出 "Impossible!" 輸入 第一行為數字n，代表有n組樣例。每組樣例有4行非負整數，空格用數字0代替。第1行和第2行為禮物的起始狀態，第3、4行目標狀態。 輸出 對於每組樣例,輸出最少的移動次數，如果不能達到輸出"Impossible!"。 樣例輸入 2 0 1 2 3 4 5 1 2 0 3 4 5 1 2 3 4 5 0 1 2 3 4 0 5 樣例輸出 2 1 Source XTUCPC2013 [cpp] /* 思路： 把矩形抽象為一個字符串 記錄狀態 看是否走過 然後用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++) { 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; }
