百度2014校园招聘笔考题——连连看判断消除算法

百度2014校园招聘笔试题——连连看判断消除算法

看到今年百度有一道笔试题考察的是《编程之美》上边的连连看游戏中消除判断算法，正好这几天查找资料学习，写了简单的连连看游戏，在这里把消除判断算法分析总结一下。

连连看游戏中允许消除的条件有两个：1. 玩家点击的两个图案相同 2. 两个图形之间存在不超过三个弯的路径。难点在于判断第二个条件。

1. 如果两个图案在一条水平线或者一条垂直线上，则有可能存在一条线可以相连的路径。

2. 如果两个图案不在一条直线上，则取其中一个图案位置为基准，另一个图案的位置可能为左上、左下、右上、右下。这种情况下，则有可能存在两条线或者三条线可以相连的路径。

分析这些情况可以发现，首先需要定义两个最基本的方法可以检查水平方向、垂直方向任意两点之间是否存在通路。然后可以通过这两种方法进行遍历整个图案分布网格区域，寻找是否存在不超过三个弯的路径实现两个图案之间相连。两条线、三条线路径分别的可能情况是横竖、竖横、横竖横、竖横竖。

两个基本方法用JS实现如下：

function CheckX(xStart, yStart, xEnd)
{
	for (var i = xStart; i != xEnd; (i<xEnd ? i++ : i--))
	{
		if (picArray[i][yStart] != " ")
		{
			return false;
		}
	}
	return true;
}
function CheckY(yStart, xStart, yEnd)
{
	for (var i = yStart; i != yEnd; (i<yEnd ? i++ : i--))
	{
		if (picArray[xStart][i] != " ")
		{
			return false;
		}
	}
	return true;
}

随后可以写出通过这两个方法来遍历寻找各个路径可能性的JS实现方法如下：

function CheckLink(P1, P2)
{
	if (P1.y > P2.y) //将P1作为基准，存储纵坐标较小的那个位置。则P2可能位于P1的正下、正左、正右、左下或者右下位置。
	{
		var temp = P1;
		P1 = P2;
		P2 = temp;
	}	
	if (CheckY(P1.y+1, P1.x, P2.y) && CheckX(P1.x, P2.y, P2.x))//调用方法检查直接相连或者两条线相连的可能路径（横、竖、横竖）
	{
		return true;
	}
	for (var i = P1.x-1; i >= 0; i--) //从P1先往左侧走，再往垂直方向，再水平方向检查三条线路径（横竖横）
	{
		if (picArray[i][P1.y] != "")
		{
			break;
		}
		if (CheckY(P1.y+1, i, P2.y) && CheckX(i, P2.y, P2.x))
		{
			return true;
		}
	}
	for (i = P1.x+1; i < maxRow+2; i++)//从P1先往右侧走，再往垂直方向，再水平方向检查三条线路径（横竖横）
	{
		if (picArray[i][P1.y] != "")
		{
			break;
		}
		if (CheckY(P1.y+1, i, P2.y) && CheckX(i, P2.y, P2.x))
		{
			return true;
		}
	}
	if (P1.x > P2.x)//将P1作为基准，存储横坐标较小的那个位置
	{
		temp = P1;
		P1 = P2;
		P2 = temp;
	}
	if (CheckX(P1.x+1, P1.y, P2.x) && CheckY(P1.y, P2.x, P2.y))//检查一条线、两条线可能路径（横、竖、竖横）
	{
		return true;
	}
	for (i = P1.y-1; i >= 0; i--)//从P1先往上走，再水平方向、垂直方向检查竖横竖路径（竖横竖）
	{
		if (picArray[P1.x][i] != "")
		{
			break;
		}
		if (CheckX(P1.x+1, i, P2.x) && CheckY(i, P2.x, P2.y))
		{
			return true;
		}
	}
	for (i = P1.y+1; i < maxCol+2; i++)//从P1先往下走，再水平方向、垂直方向检查竖横竖可能路径（竖横竖）
	{
		if (picArray[P1.x][i] != "")
		{
			break;
		}
		if (CheckX(P1.x+1, i, P2.x) && CheckY(i, P2.x, P2.y))
		{
			return true;
		}
	}
	return false;
}

这样就可以判断两个图案之间是否存在可以相连的路径了。

参考：http://bbs.****.net/topics/310100938