跳蚱蜢

BFS判重

#include<bits/stdc++.h>
using namespace std;
struct node{
  node(){}                           //手动加上只要参数个数和类型不完全相同，就可以定义任意多个构造函数，以适应不同的初始化场合。
  node(string ss, int tt){s = ss, t = tt;}             //初始化参数
  string s;
  int t;
};
//(1) map
map<string, bool> mp;                //记录已经搜索过的状态
//(2) set
// set<string> visited;
queue<node> q;
void solve(){
  while(!q.empty()){
    node now = q.front();
    q.pop();
    string s = now.s;               //当前状态
    int step = now.t;               //记录跳跃步数
    if(s == "087654321"){ cout<<step<<endl; break;}    //到目标了，输出跳跃步数
    int i;
    for(i = 0 ; i < 10 ; i++)       //找到盘子的位置i
      if(s[i] == '0') break;
    for(int j = i - 2 ; j <= i + 2 ; j++){             //4种跳法
      int k = (j + 9) % 9;          //空盘子避免负数
      if(k == i)   continue;        //这是当前状态，不用检查
      string news = s;              //全部盘子状态的临时空间
      char tmp = news[i];           //临时空间：原空盘子的位置
      news[i] = news[k];            //交换i和k盘子里的蚱蜢（编号）：第一步
      news[k] = tmp;                //交换i和k盘子里的蚱蜢（编号）：第二步
      //(1) map
      if(!mp[news]){                //判重：这个情况没有出现过
        mp[news] = true;            //标记
        q.push(node(news, step + 1));                  //入队，步数+1
      }
      //(2)set
   /* if(visited.count(news)==0){  //判重：这个情况没有出现过
        visited.insert(news);
        q.push(node(news, step + 1));
      } */
    }
  }
}
int main(){
  string s = "012345678";
  q.push(node(s, 0));
  //(1) map
  mp[s] = true;
  solve();
  return 0;
}

笔记：把圆拉直变成八数码问题，八数码有9! 种排列，蚱蜢每跳一次有4种跳法，4种跳法会延伸出16种跳法，如果不去重，20步后会有4²⁰ ≈1万亿种跳法