luogu#P2739. [USACO4.4] 棋盘游戏Shuttle Puzzle

[USACO4.4] 棋盘游戏Shuttle Puzzle

题目描述

大小为 33 的棋盘游戏里有 33 个白色棋子,33 个黑色棋子,和一个有 77 个格子一线排开的木盒子。33 个白棋子被放在一头,33 个黑棋子被放在另一头,中间的格子空着。

初始状态: WWW_BBB_ 代表空格)

目标状态: BBB_WWW

在这个游戏里有两种移动方法是允许的:

  • 你可以把一个棋子移到与它相邻的空格;
  • 你可以把一个棋子跳过一个(仅一个)与它不同色的棋子到达空格。

大小为 NN 的棋盘游戏包括 NN 个白棋子,NN 个黑棋子,还有有 2N+12N+1 个格子的木盒子。

这里是大小为 33 的棋盘游戏的解,包括初始状态,中间状态和目标状态:

WWW_BBBWW_WBBBWWBW_BBWWBWB_BWWB_BWBW_BWBWB_WBWBWBBW_WBWBBWBW_WBBWBWBW_BWBWB_WBWB_BWWB_BWBWWBB_WBWWBBBW_WWBBB_WWW

请编一个程序求解大小为 NN 的棋盘游戏(1N121 \le N \le 12)。要求用最少的移动步数实现。

输入格式

一个正整数 NN,表示棋盘游戏的大小为 NN

输出格式

输出用每一步移动的棋子移动前在棋盘的位置(位置从左到右依次为 1,2,,2N+11, 2,\cdots,2N+1)表示的序列,每个数字之间以空格分隔,每行 2020 个数(最后一行可以少于 2020 个数)。

输出的解还应当有最小的字典顺序,即如果有多组移动步数最小的解,输出第一个数最小的解;如果还有多组,输出第二个数最小的解,以此类推。

3
3 5 6 4 2 1 3 5 7 6 4 2 3 5 4

提示

题目翻译来自NOCOW。

USACO Training Section 4.3