剪枝的应用，bfs判重 蚱蜢跳——蓝桥p642

问题描述

总共有九个盘子，八只蚱蜢，且每个盘子中只能容下一只蚱蜢，蚱蜢的编号为1~8，如果蚱蜢所在的盘子紧邻着空盘子，那么该蚱蜢可以从自己的盘子跳到空盘子中，也可以隔一个盘子跳到空盘子中，问一开始状态是012345678，蚱蜢至少该跳多少步才可以被变为087654321

输入

无

输出

蚱蜢跳过的步数

问题分析：

• 题目中说的是蚱蜢在跳，但蚱蜢有很多只，这会增加编码难度，但空盘子只有一个，我们可以让盘子移动，你那么就可以规避这个问题
• 经过分析，盘子的移动方式有四种，左1，左2，右1，右2，但由于题目中这些盘子是一个圈，所以在移动时也要考虑这一因素，也就时我们常说的化曲为直，多提一句，这个移动其实是有公式的但是我不大像推，所以就用了switch语句，效果是一样的
• 之后就是本题的核心-————去重，这里我使用的时map，其实还有set，去重操作可以帮助删去大量的重复节点

#include<iostream>
#include<map>
#include<queue>
using namespace std;

struct node {
    node(){}
    node(string ss, int tt,int po) :s(ss),t(tt),pos(po){}
    string s;
    int t;   //表示步数
    int pos;  //表示当前字符串0的位置，从0开始数
};

map<string, bool>mp;
queue<node>que;

node now, nxt;

int cal(int i,int pos) {
    switch (i) {
    case 1:
        return pos + 1 > 8 ? pos+1-8-1 : pos + 1;
        break;
    case 2:
        return pos + 2 > 8 ? pos+2-8-1 : pos + 2;
        break;
    case 3:
        return pos - 1 < 0 ? pos-1+8+1 : pos - 1;
        break;
    case 4:
        return pos - 2 < 0 ? pos-2+8+1 : pos - 2;
    }
}

void bfs() {
    while (!que.empty()) {
        now = que.front();
        que.pop();
        //如果找到答案就结束循环
        if (now.s == "087654321") {
            cout << now.t << endl;
            break;
        }
        for (int i = 1; i <= 4; i++) {
            int k = cal(i, now.pos);
            nxt.pos = k;
            nxt.s = now.s;
            nxt.t = now.t + 1;
            char tmp = nxt.s[now.pos];
            nxt.s[now.pos] = nxt.s[k];
            nxt.s[k] = tmp;
            //map判重
            if (!mp[nxt.s]) {
                mp[nxt.s] = true;
                que.push(nxt);
            }
        }
    }
}

int main() {
    string s = "012345678";
    que.push(node(s, 0, 0));
    mp[s] = true;
    bfs();
    return 0;
}