青蛙跳杯子--bfs最短路

1.最短路效应求最少/最短

2.map<string,int>来代替vis标记次数

3.3种方式6种情况

#include<bits/stdc++.h>
using namespace std;
#define N 100011
typedef  long long ll;
typedef pair<ll,int> pii;
string a,b;
map<string,int> bo;
queue<string> q;
int main() {
	cin>>a>>b;
	bo[a]=1;
	for(int i=0;i<a.size();i++)
	{
		if(a[i]=='*')
		{
			if(i-3>=0)
			{
				char x=a[i-3];
				char y=a[i];
				string w=a;
				w[i-3]=y;
				w[i]=x;
				if(!bo[w]) 
				{
					bo[w]=bo[a]+1;
					q.push(w);
				}
			}
			if(i-2>=0)
			{
				char x=a[i-2];
				char y=a[i];
				string w=a;
				w[i-2]=y;
				w[i]=x;
				if(!bo[w]) 
				{
					bo[w]=bo[a]+1;
					q.push(w);
				}
			}
			if(i-1>=0)
			{
				char x=a[i-1];
				char y=a[i];
				string w=a;
				w[i-1]=y;
				w[i]=x;
				if(!bo[w]) 
				{
					bo[w]=bo[a]+1;
					q.push(w);
				}
			}
			if(i+3<a.size())
			{
				char x=a[i+3];
				char y=a[i];
				string w=a;
				w[i+3]=y;
				w[i]=x;
				if(!bo[w]) 
				{
					bo[w]=bo[a]+1;
					q.push(w);
				}
			}
			if(i+2<a.size())
			{
				char x=a[i+2];
				char y=a[i];
				string w=a;
				w[i+2]=y;
				w[i]=x;
				if(!bo[w]) 
				{
					bo[w]=bo[a]+1;
					q.push(w);
				}
			}
			if(i+1<a.size())
			{
				char x=a[i+1];
				char y=a[i];
				string w=a;
				w[i+1]=y;
				w[i]=x;
				if(!bo[w]) 
				{
					bo[w]=bo[a]+1;
					q.push(w);
				}
			}
		}
	}
	while(q.size())
	{
	string a=q.front();
	q.pop();
	if(a==b)
	{
		cout<<bo[a]-1;
		return 0;
	}
	else
	{
	for(int i=0;i<a.size();i++)
	{
		if(a[i]=='*')
		{
			if(i-3>=0)
			{
				char x=a[i-3];
				char y=a[i];
				string w=a;
				w[i-3]=y;
				w[i]=x;
				if(!bo[w]) 
				{
					bo[w]=bo[a]+1;
					q.push(w);
				}
			}
			if(i-2>=0)
			{
				char x=a[i-2];
				char y=a[i];
				string w=a;
				w[i-2]=y;
				w[i]=x;
				if(!bo[w]) 
				{
					bo[w]=bo[a]+1;
					q.push(w);
				}
			}
			if(i-1>=0)
			{
				char x=a[i-1];
				char y=a[i];
				string w=a;
				w[i-1]=y;
				w[i]=x;
				if(!bo[w]) 
				{
					bo[w]=bo[a]+1;
					q.push(w);
				}
			}
			if(i+3<a.size())
			{
				char x=a[i+3];
				char y=a[i];
				string w=a;
				w[i+3]=y;
				w[i]=x;
				if(!bo[w]) 
				{
					bo[w]=bo[a]+1;
					q.push(w);
				}
			}
			if(i+2<a.size())
			{
				char x=a[i+2];
				char y=a[i];
				string w=a;
				w[i+2]=y;
				w[i]=x;
				if(!bo[w]) 
				{
					bo[w]=bo[a]+1;
					q.push(w);
				}
			}
			if(i+1<a.size())
			{
				char x=a[i+1];
				char y=a[i];
				string w=a;
				w[i+1]=y;
				w[i]=x;
				if(!bo[w]) 
				{
					bo[w]=bo[a]+1;
					q.push(w);
				}
			}
		}
	}
	}	
	} 
	return 0;
}