青蛙跳杯子
bfs
思路:刚开始用的是dfs,但是不太行,DFS 可能会导致搜索深度过深,增加了时间复杂度,BFS 适合求解最短路径问题,BFS 在搜索过程中,首先访问距离初始节点最近的节点,因此可以保证找到的路径是最短的,所以应该选择bfs。
本题可以以*为切入点,来进行跳跃
#include<iostream>
#include<cmath>
#include<queue>
#include<algorithm>
#include<cstring>
#include<map>
using namespace std;
typedef long long ll;
string s1,s2;
//需要用这个来存储一个串如果已经被访问过就不用再跳了,不然会重复很多
map<string,bool> m;
ll bfs(int n)
{
queue<pair<string,ll>> q;
q.push({s1,0});
while(!q.empty())
{
string s=q.front().first;
//代表步数
ll num=q.front().second;
q.pop();
if(s==s2) return num;
if(m[s]) continue;
m[s]=1;
int idx=s.find('*');
string temp;
//交换左边第一个
if(idx>0)
{
temp=s;
swap(temp[idx],temp[idx-1]);
q.push({temp,num+1});
}
//交换左边第二个
if(idx>1)
{
temp=s;
swap(temp[idx],temp[idx-2]);
q.push({temp,num+1});
}
//交换左边第三个
if(idx>2)
{
temp=s;
swap(temp[idx],temp[idx-3]);
q.push({temp,num+1});
}
//交换右边第一个
if(idx<n-1)
{
temp=s;
swap(temp[idx],temp[idx+1]);
q.push({temp,num+1});
}
//交换右边第二个
if(idx<n-2)
{
temp=s;
swap(temp[idx],temp[idx+2]);
q.push({temp,num+1});
}
//交换右边第三个
if(idx<n-3)
{
temp=s;
swap(temp[idx],temp[idx+3]);
q.push({temp,num+1});
}
}
return -1;
}
int main()
{
cin>>s1>>s2;
int n=s1.size();
cout<<bfs(n)<<endl;
return 0;
}