我好™生气啊我没看题以为随便2个数都可以交换位置。。。
查看原帖
我好™生气啊我没看题以为随便2个数都可以交换位置。。。
1093323
liujiayi666楼主2025/1/23 11:38

然后调了2h写了个这个

#include<bits/stdc++.h>
using namespace std;
int n,m=123804765;
int bfs(){
	if(n==m)return 2;
	queue< pair<int,int> >q1;
	queue< pair<int,int> >q2;
	map<int,int>mp1;
	map<int,int>mp2;
	q1.push(make_pair(n,1));
	q2.push(make_pair(m,1));
	mp1[n]=1;
	mp2[m]=1;
	while(!q1.empty()&&!q2.empty()){
		int s1=q1.front().first,s2=q2.front().first,st1=q1.front().second,st2=q2.front().second;
		q1.pop();q2.pop();
		cout<<s1<<" "<<s2<<endl;
		//1
		s1=s1-(s1/(int)1e8)*(int)1e8-(s1/(int)1e7%10)*(int)1e7+(s1/(int)1e8%10)*(int)1e7+(s1/(int)1e7%10)*(int)1e8;
		if(!mp1[s1]){
			cout<<s1<<endl;
			if(mp2[s1])
				return st1+1+mp2[s1];
			mp1[s1]=st1+1;
			q1.push(make_pair(s1,st1+1));
		}
		s1=s1-(s1/(int)1e8)*(int)1e8-(s1/(int)1e7%10)*(int)1e7+(s1/(int)1e8%10)*(int)1e7+(s1/(int)1e7%10)*(int)1e8;
		//2
		s1=s1-(s1/(int)1e7%10)*(int)1e7-(s1/(int)1e6%10)*(int)1e6+(s1/(int)1e7%10)*(int)1e6+(s1/(int)1e6%10)*(int)1e7;
		if(!mp1[s1]){
			cout<<s1<<endl;
			if(mp2[s1])
				return st1+1+mp2[s1];
			mp1[s1]=st1+1;
			q1.push(make_pair(s1,st1+1));
		}
		s1=s1-(s1/(int)1e7%10)*(int)1e7-(s1/(int)1e6%10)*(int)1e6+(s1/(int)1e7%10)*(int)1e6+(s1/(int)1e6%10)*(int)1e7;
		//3
		s1=s1-(s1/(int)1e7%10)*(int)1e7-(s1/(int)1e4%10)*(int)1e4+(s1/(int)1e7%10)*(int)1e4+(s1/(int)1e4%10)*(int)1e7;
		if(!mp1[s1]){
			cout<<s1<<endl;
			if(mp2[s1])
				return st1+1+mp2[s1];
			mp1[s1]=st1+1;
			q1.push(make_pair(s1,st1+1));
		}
		s1=s1-(s1/(int)1e7%10)*(int)1e7-(s1/(int)1e4%10)*(int)1e4+(s1/(int)1e7%10)*(int)1e4+(s1/(int)1e4%10)*(int)1e7;
		//4
		s1=s1-(s1/(int)1e8%10)*(int)1e8-(s1/(int)1e5%10)*(int)1e5+(s1/(int)1e8%10)*(int)1e5+(s1/(int)1e5%10)*(int)1e8;
		if(!mp1[s1]){
			cout<<s1<<endl;
			if(mp2[s1])
				return st1+1+mp2[s1];
			mp1[s1]=st1+1;
			q1.push(make_pair(s1,st1+1));
		}
		s1=s1-(s1/(int)1e8%10)*(int)1e8-(s1/(int)1e5%10)*(int)1e5+(s1/(int)1e8%10)*(int)1e5+(s1/(int)1e5%10)*(int)1e8;
		//5
		s1=s1-(s1/(int)1e5%10)*(int)1e5-(s1/(int)1e2%10)*(int)1e2+(s1/(int)1e5%10)*(int)1e2+(s1/(int)1e2%10)*(int)1e5;
		if(!mp1[s1]){
			cout<<s1<<endl;
			if(mp2[s1])
				return st1+1+mp2[s1];
			mp1[s1]=st1+1;
			q1.push(make_pair(s1,st1+1));
		}
		s1=s1-(s1/(int)1e5%10)*(int)1e5-(s1/(int)1e2%10)*(int)1e2+(s1/(int)1e5%10)*(int)1e2+(s1/(int)1e2%10)*(int)1e5;
		//6
		s1=s1-(s1/(int)1e5%10)*(int)1e5-(s1/(int)1e4%10)*(int)1e4+(s1/(int)1e5%10)*(int)1e4+(s1/(int)1e4%10)*(int)1e5;
		if(!mp1[s1]){
			cout<<s1<<endl;
			if(mp2[s1])
				return st1+1+mp2[s1];
			mp1[s1]=st1+1;
			q1.push(make_pair(s1,st1+1));
		}
		s1=s1-(s1/(int)1e5%10)*(int)1e5-(s1/(int)1e4%10)*(int)1e4+(s1/(int)1e5%10)*(int)1e4+(s1/(int)1e4%10)*(int)1e5;
		//7
		s1=s1-(s1/(int)1e6%10)*(int)1e6-(s1/(int)1e3%10)*(int)1e3+(s1/(int)1e6%10)*(int)1e3+(s1/(int)1e3%10)*(int)1e6;
		if(!mp1[s1]){
			cout<<s1<<endl;
			if(mp2[s1])
				return st1+1+mp2[s1];
			mp1[s1]=st1+1;
			q1.push(make_pair(s1,st1+1));
		}
		s1=s1-(s1/(int)1e6%10)*(int)1e6-(s1/(int)1e3%10)*(int)1e3+(s1/(int)1e6%10)*(int)1e3+(s1/(int)1e3%10)*(int)1e6;
		//8
		s1=s1-(s1/(int)1e3%10)*(int)1e3-(s1%10)+(s1/(int)1e3%10)+(s1%10)*(int)1e3;
		if(!mp1[s1]){
			cout<<s1<<endl;
			if(mp2[s1])
				return st1+1+mp2[s1];
			mp1[s1]=st1+1;
			q1.push(make_pair(s1,st1+1));
		}
		s1=s1-(s1/(int)1e3%10)*(int)1e3-(s1%10)+(s1/(int)1e3%10)+(s1%10)*(int)1e3;
		//9
		s1=s1-(s1/(int)1e4%10)*(int)1e4-(s1/(int)1e3%10)*(int)1e3+(s1/(int)1e4%10)*(int)1e3+(s1/(int)1e3%10)*(int)1e4;
		if(!mp1[s1]){
			cout<<s1<<endl;
			if(mp2[s1])
				return st1+1+mp2[s1];
			mp1[s1]=st1+1;
			q1.push(make_pair(s1,st1+1));
		}
		s1=s1-(s1/(int)1e4%10)*(int)1e4-(s1/(int)1e3%10)*(int)1e3+(s1/(int)1e4%10)*(int)1e3+(s1/(int)1e3%10)*(int)1e4;
		//10
		s1=s1-(s1/(int)1e2%10)*(int)1e2-(s1/(int)1e1%10)*(int)1e1+(s1/(int)1e2%10)*(int)1e1+(s1/(int)1e1%10)*(int)1e2;
		if(!mp1[s1]){
			cout<<s1<<endl;
			if(mp2[s1])
				return st1+1+mp2[s1];
			mp1[s1]=st1+1;
			q1.push(make_pair(s1,st1+1));
		}
		s1=s1-(s1/(int)1e2%10)*(int)1e2-(s1/(int)1e1%10)*(int)1e1+(s1/(int)1e2%10)*(int)1e1+(s1/(int)1e1%10)*(int)1e2;
		//11
		s1=s1-(s1/(int)1e1%10)*(int)1e1-(s1%10)+(s1/(int)1e1%10)+(s1%10)*(int)1e1;
		if(!mp1[s1]){
			cout<<s1<<endl;
			if(mp2[s1])
				return st1+1+mp2[s1];
			mp1[s1]=st1+1;
			q1.push(make_pair(s1,st1+1));
		}
		s1=s1-(s1/(int)1e1%10)*(int)1e1-(s1%10)+(s1/(int)1e1%10)+(s1%10)*(int)1e1;
		//12
		s1=s1-(s1/(int)1e4%10)*(int)1e4-(s1/(int)1e1%10)*(int)1e1+(s1/(int)1e4%10)*(int)1e1+(s1/(int)1e1%10)*(int)1e4;
		if(!mp1[s1]){
			cout<<s1<<endl;
			if(mp2[s1])
				return st1+1+mp2[s1];
			mp1[s1]=st1+1;
			q1.push(make_pair(s1,st1+1));
		}
		s1=s1-(s1/(int)1e4%10)*(int)1e4-(s1/(int)1e1%10)*(int)1e1+(s1/(int)1e4%10)*(int)1e1+(s1/(int)1e1%10)*(int)1e4;
		cout<<endl;
		//1
		s2=s2-(s2/(int)1e8)*(int)1e8-(s2/(int)1e7%10)*(int)1e7+(s2/(int)1e8%10)*(int)1e7+(s2/(int)1e7%10)*(int)1e8;
		if(!mp2[s2]){
			cout<<s2<<endl;
			if(mp1[s2])
				return st2+1+mp1[s2];
			mp2[s2]=st2+1;
			q2.push(make_pair(s2,st1+1));
		}
		s2=s2-(s2/(int)1e8)*(int)1e8-(s2/(int)1e7%10)*(int)1e7+(s2/(int)1e8%10)*(int)1e7+(s2/(int)1e7%10)*(int)1e8;
		//2
		s2=s2-(s2/(int)1e7%10)*(int)1e7-(s2/(int)1e6%10)*(int)1e6+(s2/(int)1e7%10)*(int)1e6+(s2/(int)1e6%10)*(int)1e7;
		if(!mp2[s2]){
			cout<<s2<<endl;
			if(mp1[s2])
				return st2+1+mp1[s2];
			mp2[s2]=st2+1;
			q2.push(make_pair(s2,st1+1));
		}
		s2=s2-(s2/(int)1e7%10)*(int)1e7-(s2/(int)1e6%10)*(int)1e6+(s2/(int)1e7%10)*(int)1e6+(s2/(int)1e6%10)*(int)1e7;
		//3
		s2=s2-(s2/(int)1e7%10)*(int)1e7-(s2/(int)1e4%10)*(int)1e4+(s2/(int)1e7%10)*(int)1e4+(s2/(int)1e4%10)*(int)1e7;
		if(!mp2[s2]){
			cout<<s2<<endl;
			if(mp1[s2])
				return st2+1+mp1[s2];
			mp2[s2]=st2+1;
			q2.push(make_pair(s2,st1+1));
		}
		s2=s2-(s2/(int)1e7%10)*(int)1e7-(s2/(int)1e4%10)*(int)1e4+(s2/(int)1e7%10)*(int)1e4+(s2/(int)1e4%10)*(int)1e7;
		//4
		s2=s2-(s2/(int)1e8%10)*(int)1e8-(s2/(int)1e5%10)*(int)1e5+(s2/(int)1e8%10)*(int)1e5+(s2/(int)1e5%10)*(int)1e8;
		if(!mp2[s2]){
			cout<<s2<<endl;
			if(mp1[s2])
				return st2+1+mp1[s2];
			mp2[s2]=st2+1;
			q2.push(make_pair(s2,st1+1));
		}
		s2=s2-(s2/(int)1e8%10)*(int)1e8-(s2/(int)1e5%10)*(int)1e5+(s2/(int)1e8%10)*(int)1e5+(s2/(int)1e5%10)*(int)1e8;
		//5
		s2=s2-(s2/(int)1e5%10)*(int)1e5-(s2/(int)1e2%10)*(int)1e2+(s2/(int)1e5%10)*(int)1e2+(s2/(int)1e2%10)*(int)1e5;
		if(!mp2[s2]){
			cout<<s2<<endl;
			if(mp1[s2])
				return st2+1+mp1[s2];
			mp2[s2]=st2+1;
			q2.push(make_pair(s2,st1+1));
		}
		s2=s2-(s2/(int)1e5%10)*(int)1e5-(s2/(int)1e2%10)*(int)1e2+(s2/(int)1e5%10)*(int)1e2+(s2/(int)1e2%10)*(int)1e5;
		//6
		s2=s2-(s2/(int)1e5%10)*(int)1e5-(s2/(int)1e4%10)*(int)1e4+(s2/(int)1e5%10)*(int)1e4+(s2/(int)1e4%10)*(int)1e5;
		if(!mp2[s2]){
			cout<<s2<<endl;
			if(mp1[s2])
				return st2+1+mp1[s2];
			mp2[s2]=st2+1;
			q2.push(make_pair(s2,st1+1));
		}
		s2=s2-(s2/(int)1e5%10)*(int)1e5-(s2/(int)1e4%10)*(int)1e4+(s2/(int)1e5%10)*(int)1e4+(s2/(int)1e4%10)*(int)1e5;
		//7
		s2=s2-(s2/(int)1e6%10)*(int)1e6-(s2/(int)1e3%10)*(int)1e3+(s2/(int)1e6%10)*(int)1e3+(s2/(int)1e3%10)*(int)1e6;
		if(!mp2[s2]){
			cout<<s2<<endl;
			if(mp1[s2])
				return st2+1+mp1[s2];
			mp2[s2]=st2+1;
			q2.push(make_pair(s2,st1+1));
		}
		s2=s2-(s2/(int)1e6%10)*(int)1e6-(s2/(int)1e3%10)*(int)1e3+(s2/(int)1e6%10)*(int)1e3+(s2/(int)1e3%10)*(int)1e6;
		//8
		s2=s2-(s2/(int)1e3%10)*(int)1e3-(s2%10)+(s2/(int)1e3%10)+(s2%10)*(int)1e3;
		if(!mp2[s2]){
			cout<<s2<<endl;
			if(mp1[s2])
				return st2+1+mp1[s2];
			mp2[s2]=st2+1;
			q2.push(make_pair(s2,st1+1));
		}
		s2=s2-(s2/(int)1e3%10)*(int)1e3-(s2%10)+(s2/(int)1e3%10)+(s2%10)*(int)1e3;
		//9
		s2=s2-(s2/(int)1e4%10)*(int)1e4-(s2/(int)1e3%10)*(int)1e3+(s2/(int)1e4%10)*(int)1e3+(s2/(int)1e3%10)*(int)1e4;
		if(!mp2[s2]){
			cout<<s2<<endl;
			if(mp1[s2])
				return st2+1+mp1[s2];
			mp2[s2]=st2+1;
			q2.push(make_pair(s2,st1+1));
		}
		s2=s2-(s2/(int)1e4%10)*(int)1e4-(s2/(int)1e3%10)*(int)1e3+(s2/(int)1e4%10)*(int)1e3+(s2/(int)1e3%10)*(int)1e4;
		//10
		s2=s2-(s2/(int)1e2%10)*(int)1e2-(s2/(int)1e1%10)*(int)1e1+(s2/(int)1e2%10)*(int)1e1+(s2/(int)1e1%10)*(int)1e2;
		if(!mp2[s2]){
			cout<<s2<<endl;
			if(mp1[s2])
				return st2+1+mp1[s2];
			mp2[s2]=st2+1;
			q2.push(make_pair(s2,st1+1));
		}
		s2=s2-(s2/(int)1e2%10)*(int)1e2-(s2/(int)1e1%10)*(int)1e1+(s2/(int)1e2%10)*(int)1e1+(s2/(int)1e1%10)*(int)1e2;
		//11
		s2=s2-(s2/(int)1e1%10)*(int)1e1-(s2%10)+(s2/(int)1e1%10)+(s2%10)*(int)1e1;
		if(!mp2[s2]){
			cout<<s2<<endl;
			if(mp1[s2])
				return st2+1+mp1[s2];
			mp2[s2]=st2+1;
			q2.push(make_pair(s2,st1+1));
		}
		s2=s2-(s2/(int)1e1%10)*(int)1e1-(s2%10)+(s2/(int)1e1%10)+(s2%10)*(int)1e1;
		//12
		s2=s2-(s2/(int)1e4%10)*(int)1e4-(s2/(int)1e1%10)*(int)1e1+(s2/(int)1e4%10)*(int)1e1+(s2/(int)1e1%10)*(int)1e4;
		if(!mp2[s2]){
			cout<<s2<<endl;
			if(mp1[s2])
				return st2+1+mp1[s2];
			mp2[s2]=st2+1;
			q2.push(make_pair(s2,st1+1));
		}
		s2=s2-(s2/(int)1e4%10)*(int)1e4-(s2/(int)1e1%10)*(int)1e1+(s2/(int)1e4%10)*(int)1e1+(s2/(int)1e1%10)*(int)1e4;
	}
}
int main() {
	scanf("%d",&n);
	printf("%d\n",bfs()-2);
	return 0;
}

下辈子一定好好看题。。。

2025/1/23 11:38