蓝桥杯 跳蚱蜢 （bfs）

转载自：https://blog.csdn.net/wayway0554/article/details/79715658

　本题的解题关键就在于将蚱蜢在跳转换为盘子在跳。

当使用string当做每一个状态的标志时，可以用set进行判重。

#include<iostream>  
#include<cstring>   //使用memset必须加此头文件
#include<string>
#include<stdio.h>　　//使用printf必须加此头文件
#include<queue>
#include<set>
#include<algorithm>

using namespace std;

int dx[] = {1,-1,2,-2};

struct node
{
    int pos;   //0所在的下标 
    string s;　//此时的局面(字符串状态)
    int step;  //所在层数  
}p,t;

void bfs()
{
    set<string> vis;
    p.s = "012345678";
    p.pos = 0;
    p.step = 0;
    vis.insert(p.s);
    queue<node> Q;
    Q.push(p);
    
    while(!Q.empty())
    {
        t = Q.front();
        Q.pop();
        
        if(t.s == "087654321")
        {
            cout << t.step << endl;
            return;
        }
        
        for(int i = 0; i < 4; ++i)
        {
            int xx = (t.pos+dx[i]+9)%9;　　//跳完后的坐标，因为这里是环形的，所以要取模
            node nod;
            nod.s = t.s;
            swap(nod.s[t.pos], nod.s[xx]);
            
            if(vis.count(nod.s) == 0)
            {
                vis.insert(nod.s);
                nod.pos = xx;
                nod.step = t.step + 1;
                Q.push(nod);
            }
            
        }
    }
    
}


int main()
{
    bfs();
    
    
    
    return 0;
}

最终结果：20