[蓝桥杯2017初赛]跳蚱蜢 BFS

题目描述

如图所示： 有9只盘子，排成1个圆圈。其中8只盘子内装着8只蚱蜢，有一个是空盘。

我们把这些蚱蜢顺时针编号为 1~8。每只蚱蜢都可以跳到相邻的空盘中，也可以再用点力，越过一个相邻的蚱蜢跳到空盘中。
请你计算一下，如果要使得蚱蜢们的队形改为按照逆时针排列，并且保持空盘的位置不变（也就是1-8换位，2-7换位,...），至少要经过多少次跳跃？ 

输出

输出一个整数表示答案

 

答案：20

题解

1、用滚动数组表示环，( id+dir[i] +9)%9

 

这份代码跑的巨慢，要5 s ，但是能出答案

#include<iostream>

#include<queue>

#include<algorithm>

#include<set>

using namespace std;

int dir[]={,-,,-};//往 左/右 跳1格或2格

struct node

{

    int x;

    string s;//保存不同的图，同时用set去标记去重

    int cnt;

}A;

int change(string ss)

{

    int ans=;

    for(int i=;ss[i];i++)

        ans=ans*+ss[i]-'';

    return ans;

}

void bfs()

{

    queue<node>p;

    p.push(A);

    set<string>se;

    se.insert(A.s);

    while(!p.empty())

    {

        node now=p.front();

        p.pop();

        for(int i=;i<;i++)

        {

            string ss=now.s;

            int tx=now.x+dir[i];

            tx=(tx+)%;//滚动数组

            //if(ss[tx]=='0')

            {

                char h=ss[now.x];

                ss[now.x]=ss[tx];

                ss[tx]=h;

                node temp;

                temp.x=tx;

                temp.s=ss;

                temp.cnt=now.cnt+;

                if(ss=="")

                {

                    cout<<temp.cnt<<endl;

                    cout<<temp.s<<endl;

                    return ;

                }

                if(se.count(ss)==)//避免往回走，标记状态

                {

                    se.insert(ss);

                    p.push(temp);

                }

            }

        }

    }

}

int main()

{

    string str="";//初始状态

    //最终状态是 "087654321"

    A.x=;

    A.s=str;

    A.cnt=;

    bfs();

    return ;

}