宝箱密码
2023-07-30 18:50:27
发布于：浙江
17阅读
0回复
0点赞
#include<bits/stdc++.h>
using namespace std;
string nl,el;
bool vis[10010];
struct node{
string s;//现在的数
int step;//步数
};
int s_to_i(string s){
return (s[0] - '0') * 1000 + (s[1] - '0') * 100 + (s[2] - '0') * 10 + (s[3] - '0');
//把string变成四位数int
}
void bfs(){
queue<node> q;
q.push({nl,0});//把第一个数放进队列里
while(q.size()){
node ss = q.front();
q.pop();
string ns = ss.s;
int np = ss.step;
//判断是否为结束值
if(ns == el){
cout << np << endl;
break;
}
//+1
for(int i = 0;i < 4;i++){
if(ns[i] == '9'){//特殊值判断
ns[i] = '1';
}else{
ns[i]++;
}
if(!vis[s_to_i(ns)]){
vis[s_to_i(ns)] = 1;
q.push({ns,np + 1});
}
if(ns[i] == '1'){//回归到初始值再进行下一次循环
ns[i] = '9';
}else{
ns[i]--;
}
}
//-1
for(int i = 0;i < 4;i++){
if(ns[i] == '1'){//特殊值判断
ns[i] = '9';
}else{
ns[i]--;
}
if(!vis[s_to_i(ns)]){
vis[s_to_i(ns)] = 1;
q.push({ns,np + 1});
}
if(ns[i] == '9'){//回归到初始值再进行下一次循环
ns[i] = '1';
}else{
ns[i]++;
}
}
//交换
for(int i = 0;i < 3;i++){
swap(ns[i],ns[i + 1]);//交换函数
if(!vis[s_to_i(ns)]){
vis[s_to_i(ns)] = 1;
q.push({ns,np + 1});
}
swap(ns[i],ns[i + 1]);//回归到初始值再进行下一次循环
}
}
}
int main(){
freopen("lock.in","r",stdin);
freopen("lock.out","w",stdout);
int t;
cin >> t;
for(int i = 0;i < t;i++){
cin >> nl >> el;
bfs();
memset(vis,0,sizeof vis);//计算每组数据前将vis数组清空为false
}
fclose(stdin);
fclose(stdout);
return 0;
}
有帮助，赞一个