一维跳棋（BFS）

一维跳棋是一种在1×(2N+1) 的棋盘上玩的游戏。一共有N个棋子，其中N 个是黑的，N 个是白的。游戏开始前，N 个白棋子被放在一头，N 个黑棋子被放在另一头，中间的格子空着。

在这个游戏里有两种移动方法是允许的：你可以把一个棋子移到与它相邻的空格；你可以把一个棋子跳过一个（仅一个）与它不同色的棋子到达空格。

对于N=3 的情况，棋盘状态依次为：

 WWW BBB

 WW WBBB

 WWBW BB

 WWBWB B

 WWB BWB

 W BWBWB

 WBWBWB

 BW WBWB

 BWBW WB

 BWBWBW

 BWBWB W

 BWB BWW

 B BWBWW

 BB WBWW

 BBBW WW

 BBB WWW

对应的空格所在的位置（从左数）为：3 5 6 4 2 1 3 5 7 6 4 2 3 5 4。

输入格式

输入仅一个整数，表示针对N(1≤N≤10) 的取值。

输出格式

依次输出空格所在棋盘的位置，每个整数间用空格分隔，每行5 个数（每行结尾无空格，最后一行可以不满5 个数；如果有多组移动步数最小的解，输出第一个数最小的解）

样例输入

样例输出

用二进制来表示棋盘的状态

 #include <stdio.h>

 #include <string.h>

 #include <iostream>

 #include <string>

 #include <math.h>

 #include <algorithm>

 #include <vector>

 #include <stack>

 #include <queue>

 #include <set>

 #include <map>

 #include <sstream>

 const int INF=0x3f3f3f3f;

 typedef long long LL;

 using namespace std;

 int n;

 int P[(<<)*+];

 bool vis[<<][];

 struct node

 {

     int num;

     int pos;

 };

 int main()

 {

     #ifdef DEBUG

     freopen("sample.txt","r",stdin);

     #endif

     scanf("%d",&n);

     vector<node> a;

     queue<int> qe;

     int first=(<<n)-;

     int last=first<<n;

     printf("%d %d\n",first,last);

     qe.push(a.size());

     vis[first][n]=true;

     a.push_back({first,n});

     while(!qe.empty())

     {

         int id=qe.front();

         qe.pop();

         int num=a[id].num;

         int pos=a[id].pos;

         if(num==last&&pos==n)

         {

             vector<int> ans;

             for(int i=id;i;i=P[i])

             {

                 ans.push_back(*n-a[i].pos+);

             }

             reverse(ans.begin(),ans.end());

             for(int i=;i<ans.size();i++)

                 printf("%d%c",ans[i],i%==?'\n':' ');

             break;

         }

         //空格左边的棋子移动到空格位置

         if(pos<*n)

         {

             int tn=num;

             int tp=pos+;

             if(!vis[tn][tp])

             {

                 qe.push(a.size());

                 vis[tn][tp]=true;

                 P[a.size()]=id;

                 a.push_back({tn,tp});

             }

         }

         //空格右边的棋子移动到空格位置

         if(pos>)

         {

             int tn=num;

             int tp=pos-;

             if(!vis[tn][tp])

             {

                 qe.push(a.size());

                 vis[tn][tp]=true;

                 P[a.size()]=id;

                 a.push_back({tn,tp});

             }

         }

         //空格左边的棋子跳到空格位置

         if(pos<=*n-&&((num>>pos+&)^(num>>pos&)))

         {

             int tn=num^(<<pos);

             int tp=pos+;

             if(!vis[tn][tp])

             {

                 qe.push(a.size());

                 vis[tn][tp]=true;

                 P[a.size()]=id;

                 a.push_back({tn,tp});

             }

         }

         //空格左边的棋子跳到空格位置

         if(pos>=&&((num>>pos-&)^(num>>pos-&)))

         {

             int tn=num^(<<pos-);

             int tp=pos-;

             if(!vis[tn][tp])

             {

                 qe.push(a.size());

                 vis[tn][tp]=true;

                 P[a.size()]=id;

                 a.push_back({tn,tp});

             }

         }

     }

     return ;

 }

巴特西

一维跳棋（BFS）

输入格式

输出格式

样例输入

样例输出

最新文章

热门文章