ModricWang的星灵棋

时间限制: 1000 ms 内存限制: 65536 kb
总通过人数: 0 总提交人数: 0

题目描述

ModricWang上次出了两个题,可是被校园网坑了,所以这一次准备出个一题更比四题强的题来维系宇宙平衡。

星灵棋是一种流行于Aiur的棋类游戏。ModricWang经常和他的表哥Artanis下星灵棋。

星灵棋规则如下:在一个4*4的棋盘上摆放了14颗棋子,其中有7颗白色棋子,7颗黑色棋子,有两个空白地带,任何一颗黑白棋子都可以向上下左右四个方向移动到相邻的空格,这叫行棋一步,黑白双方交替走棋,任意一方可以先走,如果某个时刻使得任意一种颜色的棋子形成四个一线(包括斜线),这样的状态为目标棋局,先达到目标棋局者赢。

由于ModricWang还有很多份解题报告没有批,所以他根本不关心输赢,只想赶紧把手里这一盘下完走人。给定当前的棋局状态,请你帮ModricWang算出最少还要多少步才能下完这盘棋。

输入

只有一组评测数据。

一个4*4的初始棋局,黑棋子用B表示,白棋子用W表示,空格地带用O表示。

保证输入格式严格符合规范,总共只有4个连续的可见行,每行只有4个连续的可见字符。不存在前导空行或前导空格。

保证输入数据完全符合规则,总共有7个B,7个W和2个O。

输出

用最少的步数移动到目标棋局的步数。

输入样例

BWBO
WBWB
BWBW
WBWO

输出样例

5

HINT

可能ModricWang已经赢了

相关推荐