八数码难题

BFS 训练的好题

在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。

输入#1

283104765

输入#2

4

using namespace std;
map<string,int>vis;
struct node{
	string s;
	int t;
	node(){};
	node(string a,int b){
		s=a;
		t=b;
	}
};
queue<node>q;
bool BFS(){
	while(q.size()){
		node u = q.front();
		q.pop();
		if(u.s=="123804765"){
			cout<<u.t;
			return true;
		}
		string s=u.s;
		for(int i=0;i<9;i++){
        if(s[i]=='0')
        {
            if(i>=3&&i<=8){//向上拓展 
                swap(s[i],s[i-3]);
                if(s=="123804765"){
                    cout<<u.t+1<<endl;
                    return true;
                }
                if(vis[s]==0){
                    vis[s]=1;
                    q.push(node(s,u.t+1));
                }
                swap(s[i],s[i-3]);
            }
            if(i>=0&&i<=5)//向下拓展 
            {
                swap(s[i],s[i+3]);
                if(s=="123804765"){
                    cout<<u.t+1<<endl;
                    return true;
                }
                if(vis[s]==0){
                    vis[s]=1;
                    q.push(node(s,u.t+1));
                }
                swap(s[i],s[i+3]);
            }
            if(i%3==1||i%3==2)//向左拓展 
            {
                swap(s[i],s[i-1]); 
                if(s=="123804765"){
                    cout<<u.t+1<<endl;
                    return true;
                }
                if(vis[s]==0){
                    vis[s]=1;
                    q.push(node(s,u.t+1));
                }
                swap(s[i],s[i-1]); 
            }
            if(i%3==1||i%3==0)//向右拓展 
            {
                swap(s[i],s[i+1]); 
                if(s=="123804765"){
                    cout<<u.t+1<<endl;
                    return true;
                }
                if(vis[s]==0){
                    vis[s]=1;
                    q.push(node(s,u.t+1));
                }
                swap(s[i],s[i+1]); 
            }
            break;
        }
	 }
   }   return false;
}
int main(){
	string s;
	cin>>s;
	q.push(node(s,0));
    vis[s]=1;
	if(!BFS()){
		cout<<-1;
	}
	return 0;
}