四子连棋

题目描述

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

输入输出格式

输入格式


从文件中读入一个4\*4的初始棋局,黑棋子用B表示,白棋子用W表示,空格地带用O表示。

输出格式


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

输入输出样例

输入样例 #1

BWBO
WBWB
BWBW
WBWO

输出样例 #1

5