蓝桥杯 跳蚱蜢 （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[] = {,-,,-};

 struct node

 {

     int pos;   //0所在的下标

     string s;　//此时的局面(字符串状态)

     int step;  //所在层数

 }p,t;

 void bfs()

 {

     set<string> vis;

     p.s = "";

     p.pos = ;

     p.step = ;

     vis.insert(p.s);

     queue<node> Q;

     Q.push(p);

     while(!Q.empty())

     {

         t = Q.front();

         Q.pop();

         if(t.s == "")

         {

             cout << t.step << endl;

             return;

         }

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

         {

             int xx = (t.pos+dx[i]+)%;　　//跳完后的坐标，因为这里是环形的，所以要取模

             node nod;

             nod.s = t.s;

             swap(nod.s[t.pos], nod.s[xx]);

             if(vis.count(nod.s) == )

             {

                 vis.insert(nod.s);

                 nod.pos = xx;

                 nod.step = t.step + ;

                 Q.push(nod);

             }

         }

     }

 }

 int main()

 {

     bfs();

     return ;

 }

最终结果：20