/ OPS / 题库 /

笨笨的棋盘游戏

笨笨的棋盘游戏

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

#描述#
现在跳棋游戏开始:
1、跳棋由黑白两种棋组成,棋盘为 1\times (1+n+m)1×(1+n+m) 的线状棋盘。( nn 为黑棋数量, mm 为白棋数量)
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
Copy
现在你要做的是,给出一个最优走法,使得笨笨最快结束棋局。

##格式##
#输入格式#
输入唯独一行:nn, mm(1\le n, m\le 2001≤n,m≤200)。

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

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

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

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

样例1
样例输入1
1 1
Copy
样例输出1
STEP 0:B_W
STEP 1:_BW
STEP 2:WB_
STEP 3:W_B
Copy
##限制##
1s

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

信息

ID
3666
难度
8
分类
模拟 | 字符串 点击显示
标签
递交数
0
已通过
0
通过率
?
上传者