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
#include
#include
#include
#include
#include
#include
using namespace std;
int a[6],b[6],mmap[2][3];
string ans,s;
mapmp;
map::iterator it;
int step;
struct haha
{
int pos;//0的位置
string ss;//矩阵对应的字符串
int sp;//step 走的步数
}temp,q;
void BFS(int k,int sp)
{
int i;
queueque;
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;