BFS 八数码的变形 XTU 1156 Game

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)  
        {

补充：软件开发 , C++ ,