笨笨的棋盘游戏
测试数据来自 system/1649
背景
笨笨:“来下棋吧~~”
路人甲:“什么棋?”
笨笨:“跳棋”
路人甲:“……”
描述
现在跳棋游戏开始:
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_,也就是说,棋局中_出现得越靠左越好。(可以选择无视这句话……)