跳蚱蜢（bns）

题目

        如下图所示： 有 $9$ 只盘子，排成 $1$ 个圆圈。 其中 $8$ 只盘子内装着 $8$ 只蚱蜢，有一个是空盘。 我们把这些蚱蜢顺时针编号为 $1$ ~ $8$。

        每只蚱蜢都可以跳到相邻的空盘中， 也可以再用点力，越过一个相邻的蚱蜢跳到空盘中。

        请你计算一下，如果要使得蚱蜢们的队形改为按照逆时针排列， 并且保持空盘的位置不变（也就是 1-81-8换位，2-72-7换位,...），至少要经过多少次跳跃？

思路

代码

#include<iostream>
#include<queue>
#include<set>
#include<string.h>
using namespace std;
char *start = "012345678";
char *target = "087654321";
 
struct StateAndLevel{
    char *state;
    int level;
    int pos0;
    StateAndLevel(char *_state,int _level,int _pos0)
    :state(_state),level(_level),pos0(_pos0){}
     
};
queue<StateAndLevel> q;
//写一个比较器，说明规
struct cmp{
  bool operator()(char *a,char *b){
    return strcmp(a,b) < 0;//大于和小于都行？
  }
};
set<char*,cmp> allstate;//去重，重载cmp
 
void swap(char *state,int pos0,int newpos0){
    int temp = state[pos0];
    state[pos0] = state[newpos0];
    state[newpos0] = temp;
}
int main(){
    q.push(StateAndLevel(start,0,0));
    while(!q.empty()){
        StateAndLevel  sal = q.front();
        char  *sta = sal.state;
        int lev = sal.level;
        if(strcmp(sta,target) == 0){
            cout<<lev<<endl;
            return 0;
        }
        int pos0 = sal.pos0;
        allstate.insert(sta);
         
        //添加右一neighbor
        char *newstate = (char*)malloc(9*sizeof(char));
        strcpy(newstate,sta);
        int newpos0 = (1+9 + pos0) % 9 ;
        swap(newstate,pos0,newpos0);
        if(allstate.find(newstate) == allstate.end()){
            allstate.insert(newstate);
            q.push(StateAndLevel(newstate,lev+1,newpos0));
        }
         
        //添加右二neighbor
        char *newstate1 = (char*)malloc(9*sizeof(char));
        strcpy(newstate1,sta);
        int newpos1 = (2+9 + pos0) % 9 ;
        swap(newstate1,pos0,newpos1);
        if(allstate.find(newstate1) == allstate.end()){
            allstate.insert(newstate1);
            q.push(StateAndLevel(newstate1,lev+1,newpos1));
        }
 
        //添加左一neighbor
        char *newstate2 = (char*)malloc(9*sizeof(char));
        strcpy(newstate2,sta);
        int newpos2 = (-1+9 + pos0) % 9 ;
        swap(newstate2,pos0,newpos2);
        if(allstate.find(newstate2) == allstate.end()){
            allstate.insert(newstate2);
            q.push(StateAndLevel(newstate2,lev+1,newpos2));
        }
 
        //添加左二neighbor
        char *newstate3 = (char*)malloc(9*sizeof(char));
        strcpy(newstate3,sta);
        int newpos3 = (-2+9 + pos0) % 9 ;
        swap(newstate3,pos0,newpos3);
        if(allstate.find(newstate3) == allstate.end()){
            allstate.insert(newstate3);
            q.push(StateAndLevel(newstate3,lev+1,newpos3));
        }
         
        q.pop();
    }
     
    return 0;
}