蓝桥杯-跳蚂蚱

题目描述

本题为填空题,只需要算出结果后,在代码中使用输出语句将所填结果输出即可。

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

蓝桥杯-跳蚂蚱

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

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

运行限制
最大运行时间:1s
最大运行内存: 128M

参考

https://blog.csdn.net/wayway0554/article/details/79715658

思路

跳法:左1格、左2格、右1格、右2格
策略:我们将当前的局面用字符串保存,例如初始的局面是“012345678”,用广搜的办法来搜索最小的步数。
去重:广搜深搜都有剪枝的问题,目的就是去除不可能的分支,提高效率,这里我用了STL的set容器来判重,在搜到一种局面后,在set里对这个局面进行查找,如果存在的话,就说明已经搜索过这个局面了,不用重复搜索。如果没有,则加入set。
终止:当搜到”087654321”这个局面的时候,结束,输出最小步数。

代码

#include<iostream>  
#include<memory.h>
#include<stack>
#include<string>
#include<cmath>
#include<map>
#include<algorithm> 
#include<sstream>
#include<set>
#include<queue>
//青蛙跳格子,我采用裸广搜的方法,几秒可以出答案,但是有时间限制就不行了
//将青蛙跳看作是,圆盘跳动,这样就只有一个变量在变化了 
//将圆盘看成是0,初始序列用012345678表示,在广搜的时候用set判一下重 
using namespace std;
struct node
{
    string str;//局面字符串
    int pos;//0的位置也就是空盘子
    int step;//到达这个局面的步数
    node(string str, int pos, int step) :str(str), pos(pos), step(step) {}

};
int N = 9;
set<string> visited;//已经搜索过的局面
queue<node> q;//用户来广搜的队列
void insertq(node no, int i)//node为新的局面,i为移动方式
{
    string s = no.str;
    swap(s[no.pos], s[(no.pos + i + 9) % 9]);//将0和目标位置数字交换
    //取模是为了模拟循环的数组
    if (visited.count(s) == 0)//如果没有搜索过这个局面
    {
        visited.insert(s);
        node n(s, (no.pos + i + 9) % 9, no.step + 1);
        q.push(n);
    }
}
int main()
{
    node first("012345678", 0, 0);
    q.push(first);

    while (!q.empty())
    {
        node temp = q.front();
        if (temp.str == "087654321")
        {
            cout << temp.step;
            break;
        }
        else
        {
            //四种跳法
            insertq(temp, 1);
            insertq(temp, -1);
            insertq(temp, 2);
            insertq(temp, -2);
            q.pop();
        }

    }


}

上一篇:token验证-微信公众平台开发3(asp.net)


下一篇:Ant Design Pro V4.5 从服务器请求菜单图标不显示解决