2021-04-15 算法谜题 一维数组 机械迷城_机械迷城跳棋

记录一下遇到的一道算法题。。故事是这样的–那天在玩一个经典的解谜游戏《机械迷城》然后遇到这个场景，喜欢思考的我把它和数组&&链表&&算法联系到了一起，但是基础薄弱搞不来，就去那些技术交流群里请教别人，挺感谢的

然后就在刷知乎的时候看到了下面这张图 底下的“一维跳棋” 点起了我解决它的强烈欲望。

正文开始

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

在这个游戏里有两种移动方法是允许的：你可以把一个棋子移到与它相邻的空格；你可以把一个棋子跳过一个（仅一个）与它不同色的棋子到达空格。就是自己只能通过自己的棋子作为炮台跳
虽然没有游戏里面的生动，这边用文字描述一下过程

对应的空格所在的位置（从左数）为：3 5 6 4 2 1 3 5 7 6 4 2 3 5 4。
1-2-3-4-5-6-7
WWW BBB			对应的空格所在的位置（从左数）为：4
WW WBBB			对应的空格所在的位置（从左数）为：3		
WWBW BB			对应的空格所在的位置（从左数）为：5
WWBWB B			对应的空格所在的位置（从左数）为：6
WWB BWB			对应的空格所在的位置（从左数）为：4
W BWBWB			对应的空格所在的位置（从左数）为：2
WBWBWB			对应的空格所在的位置（从左数）为：1
BW WBWB			对应的空格所在的位置（从左数）为：3
BWBW WB			对应的空格所在的位置（从左数）为：5
BWBWBW			对应的空格所在的位置（从左数）为：7(最后一个)
BWBWB W			对应的空格所在的位置（从左数）为：6
BWB BWW			对应的空格所在的位置（从左数）为：4
B BWBWW			对应的空格所在的位置（从左数）为：2
BB WBWW			对应的空格所在的位置（从左数）为：3
BBBW WW			对应的空格所在的位置（从左数）为：5
BBB WWW			对应的空格所在的位置（从左数）为：4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

我们可以用输入输出来描述这个题目
输入格式

输入仅一个整数，表示针对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