跳蚱蜢(bnf)-添加了封装函数和部分注释

题目

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

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

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

思路

        ①找到始态、终态，确定入队的结构体

        ②使用广度优先搜索遍历判断

代码

#include#include#include#includeusing 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 q;

//写一个运算符-比较器
struct cmp{
  bool operator()(char *a,char *b){
    return strcmp(a,b) < 0;
  }
};

//定义集合，目的去重，重载cmp
set allstate;

//定义交互函数
void swap(char *state,int pos0,int newpos0){
    char temp = state[pos0];
    state[pos0] = state[newpos0];
    state[newpos0] = temp;
}

//定义添加邻居点函数
void addneighbor(StateAndLevel sal,int inter_loc){
    char *newstate = (char*)malloc(9*sizeof(char));
    strcpy(newstate,sal.state);
    int pos0 = sal.pos0;
    int newpos0 = (inter_loc + 9 + pos0) % 9 ;
    swap(newstate,pos0,newpos0);
    if(allstate.find(newstate) == allstate.end()){
        allstate.insert(newstate);
        q.push(StateAndLevel(newstate,sal.level+1,newpos0));
    }
}

int main(){
    //初始状态入栈
    q.push(StateAndLevel(start,0,0));
    allstate.insert(start);

    while(!q.empty()){
        //判断状态是否为最终状态，若是输入跳跃次数，否则继续广度遍历
        StateAndLevel  sal = q.front();
        if(strcmp(sal.state,target) == 0){
            cout<<sal.level<<endl;
            return 0;
        }

        //添加右一neighbor
        addneighbor(sal,1);
         
        //添加右二neighbor
        addneighbor(sal,2);
 
        //添加左一neighbor
        addneighbor(sal,-1);
 
        //添加左二neighbor
        addneighbor(sal,-2);

        //出栈 
        q.pop();
    }
    return 0;
}