蓝桥杯2017年第八届真题-青蛙跳杯子 （C++代码）

解题思路:就是个典型广搜就可以了

注意事项:这狗比垃圾水题一道，题没读完就开始解题，

               然后有个条件没看到一直不对

参考代码:

#include<iostream>
#include<queue>
#include<map>
#include<string>
using namespace std;
map<string,int>vis;
struct node{
 string s;
 int we,step;
};
string ss;
queue<node>q;
int dir[6]={1,-1,2,-2,3,-3};
int main()
{
 node st;
 cin>>ss;
 cin>>st.s;
 for(int i=0;i<ss.size();i++)
 {
  if(st.s[i]=='*')
    st.we=i;
 }
 st.step=0;
 if(st.s==ss)
 {
 
 cout<<st.step;
    return 0;
 }
 node h,t;
 vis[t.s]=1;
 q.push(st);
    while(!q.empty())
 {
  h=q.front();
  q.pop();
  for(int i=0;i<6;i++)
  {
      t.we=h.we+dir[i];
  if(t.we>=0&&t.we<ss.length())
  {
  
   t.s=h.s;
   t.step=h.step+1;
   swap(t.s[t.we],t.s[h.we]);
   if(!vis[t.s])
   {
    
   vis[t.s]=1;
   if(t.s==ss)
   {
    cout<<t.step;
    return 0;
   }
   q.push(t);
      }
      }
    }
  }
 return 0;
}