一.题目描述
二.输入描述
输入为 2 行,2 个串,表示初始局面和目标局面。我们约定,输入的串的长度不超过 15。
三.输出描述
输出要求为一个整数,表示至少需要多少步的青蛙跳。
四.问题分析
注意:空杯子只有一个
使用广度优先搜索
暴力枚举
//青蛙跳杯子
#include <bits/stdc++.h>
using namespace std;
string s1,s2;
int n;
int d[]={-3,-2,-1,1,2,3};
map <string,int> ans;
int bfs(){
queue <string> q;
q.push(s1);
ans[s1]=0;
while(!q.empty()){
string s3=q.front();
q.pop();
int cnt=ans[s3];
int x=(int)s3.find('*');
for(int i=0;i<6;i++){
int z=x+d[i];
if(z>=0&&z<n){
swap(s3[x],s3[z]);
if(ans.count(s3)==0){
ans[s3]=cnt+1;
if(s3==s2){
return ans[s3];
}
q.push(s3);
}
swap(s3[x],s3[z]);
}
}
}
return -1;
}
int main(int argc, const char * argv[]) {
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>s1>>s2;
n=(int)s1.size();
cout<<bfs()<<'\n';
return 0;
}