解题思路

数据结构设计

• 使用字符串s存储当前数字排列状态
• 将光标位置作为特殊字符追加到字符串末尾
• 使用map数据结构记录已访问的状态，避免重复计算

搜索策略

采用广度优先搜索(BFS)算法遍历所有可能的状态：

1. 从初始状态开始搜索
2. 每次扩展当前状态的所有合法操作
3. 使用map记录已访问状态
4. 遇到目标状态立即返回当前步数

优化剪枝策略

关键实现步骤

1. 初始化队列和访问标记map
2. 对每个状态检查2,3,4,5位置：
   • 若与目标不同，只生成up/down操作的新状态
   • 若与目标相同，才生成left/right操作的新状态
3. 遇到目标状态立即返回
4. 队列为空则表示无解

复杂度分析

• 时间复杂度：O(N!)，N为数字数量，但因剪枝优化实际运行效率更高
• 空间复杂度：O(N!)，使用map存储访问状态

#include <iostream>
#include <map>
#include <string> 
#include <queue> 
using namespace std;
struct point
{
	int step;
	string s;
};
string e;
map<string,int> my;
queue<point> q;
int BFS(point st)
{
	point t,tt; string ss; int i;
	while(!q.empty()) q.pop();
	q.push(st);  my[st.s]=1;
	while(!q.empty())
	{
		t=q.front(); q.pop();
		
		for(ss=t.s,i=0;i<6;i++)
			if(ss[i]!=e[i]) break;
		if(i==6) return t.step;
		ss=t.s; swap(ss[0],ss[ss[6]-'0']);//Swap0：
		if(!my.count(ss))
		{
			tt.s=ss; tt.step=t.step+1;
			q.push(tt); my[ss]=1;
		}
		ss=t.s; swap(ss[5],ss[ss[6]-'0']); //Swap1
		if(!my.count(ss))
		{
			tt.s=ss; tt.step=t.step+1;
			q.push(tt); my[ss]=1;
		}
		ss=t.s; if(ss[ss[6]-'0']!='9'&&ss[ss[6]-'0']!=e[ss[6]-'0']) ss[ss[6]-'0']+=1; //Up：
		if(!my.count(ss))
		{
			tt.s=ss; tt.step=t.step+1;
			q.push(tt); my[ss]=1;
		}
		ss=t.s; if(ss[ss[6]-'0']!='0'&&ss[ss[6]-'0']!=e[ss[6]-'0']) ss[ss[6]-'0']-=1;//Down： 
		if(!my.count(ss))
		{
			tt.s=ss; tt.step=t.step+1;
			q.push(tt); my[ss]=1;
		}
		ss=t.s; 
		if(ss[6]-'0'!=0)//left
		{
			if(ss[6]!='5') //1 2 3 4位置相同才能移动光标 
			{
				if(ss[ss[6]-'0']==e[ss[6]-'0']) ss[6]-=1; 
			}
			else ss[6]-=1;
		}
		if(!my.count(ss))
		{
			tt.s=ss; tt.step=t.step+1;
			q.push(tt); my[ss]=1;
		}
		ss=t.s; 
		if(ss[6]-'0'!=5)//Right
		{
			if(ss[6]!='0') //1 2 3 4位置相同才能移动光标 
			{
				if(ss[ss[6]-'0']==e[ss[6]-'0']) ss[6]+=1; 
			}
			else ss[6]+=1;
		}
		if(!my.count(ss))
		{
			tt.s=ss; tt.step=t.step+1;
			q.push(tt); my[ss]=1;
		}	
	}
}
int main(int argc, char *argv[])
{
	point st;
	while(cin>>st.s>>e)
	{
		my.clear();
		st.s+='0'; st.step=0;
		cout<<BFS(st)<<endl;
	}
	return 0;
}