/ Vijos / 题库 /

笨笨的棋盘游戏

笨笨的棋盘游戏

背景

笨笨:“来下棋吧~~”
路人甲:“什么棋?”
笨笨:“跳棋”
路人甲:“……”

描述

现在跳棋游戏开始:
1、跳棋由黑白两种棋组成,棋盘为 \(1\times (1+n+m)\) 的线状棋盘。( \(n\) 为黑棋数量, \(m\) 为白棋数量)
2、刚开始黑棋在左边(用B表示),白棋在右边(用W表示),双方中间有一空格。

3、每次只能走一个棋子,走棋方式只有移动和跳越两种:①移动:将棋子向旁边的空格移动。②跳跃:将棋子越过旁边的棋子抵达空格。

4、当空格左边都是白棋,右边都是黑棋时游戏结束。

下面是游戏进行的一个例子:
黑棋:3 白棋:3

STEP    0:BBB_WWW
STEP    1:BB_BWWW
STEP    2:BBWB_WW
STEP    3:BBWBW_W
STEP    4:BBW_WBW
STEP    5:B_WBWBW
STEP    6:_BWBWBW
STEP    7:WB_BWBW
STEP    8:WBWB_BW
STEP    9:WBWBWB_
STEP   10:WBWBW_B
STEP   11:WBW_WBB
STEP   12:W_WBWBB
STEP   13:WW_BWBB
STEP   14:WWWB_BB
STEP   15:WWW_BBB

现在你要做的是,给出一个最优走法,使得笨笨最快结束棋局。

格式

输入格式

输入唯独一行:\(n\), \(m\)(\(1\le n, m\le 200\))。

输出格式

输出有多行,为最少步数结束的棋局。

格式如下:
STEP-----:当前局势
具体请见描述及样例。

若有多解,输出字典序靠后的。

若不明白 W、B、_ 这三个字符的顺序的,请见注释 Hint。

样例1

样例输入1

1 1

样例输出1

STEP    0:B_W
STEP    1:_BW
STEP    2:WB_
STEP    3:W_B

限制

1s

提示

W、B和_的顺序是BW_,也就是说,棋局中_出现得越靠左越好。(可以选择无视这句话……)

信息

ID
1649
难度
8
分类
模拟 | 字符串 点击显示
标签
递交数
349
已通过
28
通过率
8%
被复制
2
上传者

相关

在下列训练计划中:

RP++分类题库

在下列比赛中:

笨笨工作室告别十月模拟赛