首页 > 其他 > 详细

一维跳棋(BFS)

时间:2020-01-14 09:07:23      阅读:235      评论:0      收藏:0      [点我收藏+]

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

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

对于N=3 的情况,棋盘状态依次为:

 1 WWW BBB
 2 WW WBBB
 3 WWBW BB
 4 WWBWB B
 5 WWB BWB
 6 W BWBWB
 7 WBWBWB
 8 BW WBWB
 9 BWBW WB
10 BWBWBW
11 BWBWB W
12 BWB BWW
13 B BWBWW
14 BB WBWW
15 BBBW WW
16 BBB WWW

对应的空格所在的位置(从左数)为:3 5 6 4 2 1 3 5 7 6 4 2 3 5 4。

输入格式

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

输出格式

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

样例输入

4 

样例输出

4 6 7 5 3
2 4 6 8 9
7 5 3 1 2
4 6 8 7 5
3 4 6 5

 

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

 

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <iostream>
  4 #include <string>
  5 #include <math.h>
  6 #include <algorithm>
  7 #include <vector>
  8 #include <stack>
  9 #include <queue>
 10 #include <set>
 11 #include <map>
 12 #include <sstream>
 13 const int INF=0x3f3f3f3f;
 14 typedef long long LL;
 15 using namespace std;
 16 
 17 int n;
 18 int P[(1<<20)*21+5];
 19 bool vis[1<<20][21];
 20 struct node
 21 {
 22     int num;
 23     int pos;
 24 };
 25 
 26 int main()
 27 {
 28     #ifdef DEBUG
 29     freopen("sample.txt","r",stdin);
 30     #endif
 31     
 32     scanf("%d",&n); 
 33     vector<node> a;
 34     queue<int> qe;
 35     int first=(1<<n)-1;
 36     int last=first<<n;
 37     printf("%d %d\n",first,last); 
 38     qe.push(a.size());
 39     vis[first][n]=true;
 40     a.push_back({first,n});
 41     while(!qe.empty())
 42     {
 43         int id=qe.front();
 44         qe.pop();
 45         int num=a[id].num;
 46         int pos=a[id].pos;
 47         if(num==last&&pos==n)
 48         {
 49             vector<int> ans;
 50             for(int i=id;i;i=P[i])
 51             {
 52                 ans.push_back(2*n-a[i].pos+1);
 53             }
 54             reverse(ans.begin(),ans.end());
 55             for(int i=0;i<ans.size();i++)
 56                 printf("%d%c",ans[i],i%5==4?\n: );
 57             break;
 58         }
 59         //空格左边的棋子移动到空格位置
 60         if(pos<2*n)
 61         {
 62             int tn=num;
 63             int tp=pos+1;
 64             if(!vis[tn][tp])
 65             {
 66                 qe.push(a.size());
 67                 vis[tn][tp]=true;
 68                 P[a.size()]=id;
 69                 a.push_back({tn,tp});
 70             }
 71         }
 72         //空格右边的棋子移动到空格位置
 73         if(pos>0)
 74         {
 75             int tn=num;
 76             int tp=pos-1;
 77             if(!vis[tn][tp])
 78             {
 79                 qe.push(a.size());
 80                 vis[tn][tp]=true;
 81                 P[a.size()]=id;
 82                 a.push_back({tn,tp});
 83             }
 84         } 
 85         //空格左边的棋子跳到空格位置
 86         if(pos<=2*n-2&&((num>>pos+1&1)^(num>>pos&1)))
 87         {
 88             int tn=num^(3<<pos);
 89             int tp=pos+2;
 90             if(!vis[tn][tp])
 91             {
 92                 qe.push(a.size());
 93                 vis[tn][tp]=true;
 94                 P[a.size()]=id;
 95                 a.push_back({tn,tp});
 96             }
 97         }
 98         //空格左边的棋子跳到空格位置
 99         if(pos>=2&&((num>>pos-1&1)^(num>>pos-2&1)))
100         {
101             int tn=num^(3<<pos-2);
102             int tp=pos-2;
103             if(!vis[tn][tp])
104             {
105                 qe.push(a.size());
106                 vis[tn][tp]=true;
107                 P[a.size()]=id;
108                 a.push_back({tn,tp});
109             }
110         }
111     }
112     return 0;
113 }

 

-

一维跳棋(BFS)

原文:https://www.cnblogs.com/jiamian/p/12189981.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!