四子连棋(Four in a Row)

题目描述

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

输入格式

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

输出格式

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

样例输入 #1

BWBO
WBWB
BWBW
WBWO

样例输出 #1

5

数据范围

棋盘大小固定为 $4 \times 4$，包含 $7$ 颗黑棋（B）、$7$ 颗白棋（W）和 $2$ 个空格（O）。数据保证有解。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1700。

测试点分布

出处：原题链接