1. 首页
  2. 代码宅, 广度优先搜索, 搜索算法

【CodeVS 1004 四子连棋】

题目描述 Description

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

输入描述 Input Description

从文件中读入一个4*4的初始棋局,黑棋子用B表示,白棋子用W表示,空格地带用O表示
输出描述 Output Description

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

样例输入 Sample Input

BWBO
WBWB
BWBW
WBWO

样例输出 Sample Output

5

把每个棋盘搞个hash值存起来判重用,然后注意要交替下黑白棋,所以对于每一个状态还要看它跟上一个状态移动的棋子颜色是否相同,之后BFS即可,代码稍冗长。

下面是代码:

 

评分 0, 满分 5 星
0
0
看完收藏一下,下次也能找得到
上一篇:
:下一篇

发表评论

gravatar

*

沙发空缺中,还不快抢~