石子谜题
2025-08-03 20:32:36
发布于:浙江
#include<bits/stdc++.h>
using namespace std;
unordered_map<string,int> mp;
int main(){
int n;
cin>>n;
string a,b;
cin>>a>>b;
a = a + "..";
b = b + "..";
mp[a] = 0;
queue<string> q;
q.push(a);
while(q.size()){
string u = q.front();
q.pop();
int id = 0;//空位
//寻找空位
for(int i=0;i<u.size();i++){
if(u[i]=='.'){
id = i; // id id+1
break;
}
}
//寻找两个石头
for(int i=0;i<u.size()-1;i++){
if(u[i]!='.' && u[i+1]!='.'){
string y = u;
//交换石头和空位的位置
swap(y[i],y[id]);
swap(y[i+1],y[id+1]);
//如果哈希表当中没有存,也就说明没有这个状态,你可以转移
if(mp.find(y)==mp.end()){
mp[y] = mp[u]+1;
q.push(y);
}
}
}
}
if(mp.find(b)==mp.end())cout<<-1;
else cout<<mp[b];
return 0;
}
全部评论 1
你是真敢发,集训的是吧
2天前 来自 浙江
0不是呀
2天前 来自 浙江
0啊,我们集训的今天刚做了这道题
2天前 来自 浙江
0是吗,那凑巧了
2天前 来自 浙江
0
有帮助,赞一个