lanqiao OJ 102 青蛙跳杯子

#include<iostream>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
using namespace std ;
struct node{
  string s ; int t ;
  node(string ss ,int tt) {
    s = ss , t = tt ;
  }
};
string st1 , st2 ;
queue<node> q;
map<string,bool>  mp ;
void bfs(){
  while(!q.empty()){
    node now = q.front() ;
    q.pop() ;
    if(now.s == st2) {
      cout << now.t << endl ;
      break ;
    }
    int i  ;
    for(i = 0 ; i < st1.size(); i ++){
      if(now.s[i] == '*') break ;
    } 
      
    for(int j = i-3 ; j <= i +3 ; j ++){
      if(j < 0 || j >= st1.size() || i == j) continue ;
      string ss = now.s ;
      char tmp = ss[i];
      ss[i] = ss[j] ;
      ss[j] = tmp ;
      if(mp[ss]) continue ;
      else {
        mp[ss] = true ;
        q.push(node(ss,now.t + 1)) ;
      }
    }
  }
}
 
int main(){
  cin >> st1 >> st2 ;
//  cout << st1 << endl  << st2 << endl ;
  q.push(node(st1,0)) ;
  mp[st1] = true;
  bfs();
  return 0 ;
}