60分求调,新奇做法
查看原帖
60分求调,新奇做法
1389641
_Kenba_楼主2024/12/10 21:28
#include<bits/stdc++.h>
using  namespace std;
string a,a1="012345678";
char al;
queue<string> q;
map<string,string> m;
map<string,string> mp;
string sc[1000];
int temp=0;
void A(string x){
	string xx=x;
	x[0]=xx[3],x[1]=xx[0],x[2]=xx[1],x[3]=xx[6],x[4]=xx[4],x[5]=xx[2],x[6]=xx[7],x[7]=xx[8],x[8]=xx[5];
	if(m.count(x)==0){
		q.push(x);
		mp[m[xx]+'A']=x;
		m[x]=m[xx]+'A';
	}
}
void B(string x){
	string xx=x;
	x[0]=xx[0],x[1]=xx[1],x[2]=xx[2],x[3]=xx[5],x[4]=xx[3],x[5]=xx[4],x[6]=xx[6],x[7]=xx[7],x[8]=xx[8];
	if(m.count(x)==0){
		q.push(x);
		mp[m[xx]+'B']=x;
		m[x]=m[xx]+'B';
	}
}
void bfs(){
	q.push(a);
	m[a]="";
	mp[""]=a;
	while(!q.empty()){
		A(q.front());
		B(q.front());
		if(m.count(a1)==1){
			cout<<m[a1].size()<<endl;
			string str=m[a1];
			cout<<a[0]<<" "<<a[1]<<" "<<a[2]<<endl;
    		cout<<a[3]<<" "<<a[4]<<" "<<a[5]<<endl;
			cout<<a[6]<<" "<<a[7]<<" "<<a[8]<<endl<<endl;
			while(str!=""){
				sc[++temp]=mp[str];
				str=m[mp[str]].substr(0,m[mp[str]].size()-1); 
			}
			for(int i=temp;i>=1;i--){
				cout<<sc[i][0]<<" "<<sc[i][1]<<" "<<sc[i][2]<<endl;
				cout<<sc[i][3]<<" "<<sc[i][4]<<" "<<sc[i][5]<<endl;
				cout<<sc[i][6]<<" "<<sc[i][7]<<" "<<sc[i][8]<<endl<<endl;
			}
			return;
		}
		q.pop();
	}
	cout<<"UNSOLVABLE";
	return;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	for(int i=1;i<=9;i++){
		cin>>al;
		a+=al;
	}
	bfs();
	return 0; 
}
2024/12/10 21:28
加载中...