吴昊品游戏核心算法Round4——连连看AI（用BFS+STL实现）（HDOJ1175）吴昊系列

随着Flash应用的流行，网上出现了多种在线Flash版本“连连看”。如“水晶连连看”、“果蔬连连看”等，流行的“水晶连连看”以华丽界面吸引了一大批的女性玩家。

规则如下：第一次使用鼠标点击棋盘中的棋子，该棋子此时为“被选中”，以特殊方式显示；再次以鼠标点击其他棋子，若该棋子与被选中的棋子图案相同，且把第一个棋子到第二个棋子连起来，中间的直线不超过3根，则消掉这一对棋子，否则第一颗棋子恢复成未被选中状态，而第二颗棋子变成被选中状态。

下面我来品析的这个AI实际上实现的是一个查询功能，属于连连看的一个小“作弊工具”，使用它之后，可以判断当前局面是否还有可以消去的“图形对”（实际上，该小工具还可以搜索到任意的一种这样的“图形对”并提示可以删去，当然，这些都是大同小异了）

我们利用BFS（宽度优先搜索）进行，并且，利用STL里面的队列queue结构来存储每一种结果。（这种或者类似的方法，在推箱子游戏的AI中也是比较常见的）

下面，我来给出HDOJ1175关于此问题的介绍和一些input和output。

ProblemDescription——“连连看”相信很多人都玩过。没玩过也没关系，下面我给大家介绍一下游戏规则：在一个棋盘中，放了很多的棋子。如果某两个相同的棋子，可以通过一条线连起来（这条线不能经过其它棋子），而且线的转折次数不超过两次，那么这两个棋子就可以在棋盘上消去。不好意思，由于我以前没有玩过连连看，咨询了同学的意见，连线不能从外面绕过去的，但事实上这是错的。现在已经酿成大祸，就只能将错就错了，连线不能从外围绕过（吴昊评注：这个也算是连连看的一个变种吧！）。玩家鼠标先后点击两块棋子，试图将他们消去，然后游戏的后台判断这两个方格能不能消去。现在你的任务就是写这个后台程序（吴昊评注：前台的绚丽靠UI和美工，后台的绚丽靠数据结构和算法）。

Input——输入数据有多组。每组数据的第一行有两个正整数n,m(0

Output——每一组输入数据对应一行输出。如果能消去则输出"YES",不能则输出"NO"。

亮点如下：

（1）上下左右四个方向的标识，采用一个二维数组，这也是一种常用技巧dir[4][2].

（2）采用STL队列容器，装载每一个可能的点。

（3）在BFS中，每相邻两个点放在一起判断，定期更新每个点处拐弯次数的最小值，这一点很不错。