这是写连连看时用来判断两点是否可以消除的核心代码。
整体思路是枚举判断：先尝试直线连通（零拐点），再尝试一个拐点，最后尝试两个拐点。三种情况只要有一种成立，就说明两点可以消除。下面给出 C++ 版本的实现。
int data[13][8];
class Point2D
{
public:
int x;
int y;
Point2D(int xx, int yy):x(xx),y(yy){}
Point2D() :x(0), y(0){}
}
class searchAlg
{
public:
int search_0(Point2D pre, Point2D las, queue<Point2D> &tmp)
{
/*
二维坐标0代表 空
搜索0拐点
return 0 代表未找到
return N N代表路径数(两点差值)
相邻返回1 隔一个返回2 以此类推
*/
int x_pre = pre.x;
int y_pre = pre.y;
int x_las = las.x;
int y_las = las.y;
//x变量
if (y_pre == y_las)
{
int min = x_pre > x_las ? x_las : x_pre;
int max = x_pre < x_las ? x_las : x_pre;
tmp.push(Point2D(x_pre, y_pre));
if (x_pre>x_las)
{
for (int x = max - 1; x > min; x--)
{
if (data[x][y_pre] == 0)
{
tmp.push(Point2D(x, y_pre));
}
else
{
return 0;
}
}
}
if (x_pre <= x_las) //等价
//else
{
for (int x = min + 1; x < max; x++)
{
if (data[x][y_pre] == 0)
{
tmp.push(Point2D(x, y_pre));
}
else
{
return 0;
}
}
}
return (max - min); //代表队列多少个数据
}
///y变量
if (x_pre == x_las)
{
int min = y_pre > y_las ? y_las : y_pre;
int max = y_pre < y_las ? y_las : y_pre;
tmp.push(Point2D(x_pre, y_pre));
if (y_pre>y_las)
{
for (int y = max - 1; y > min; y--)
{
if (data[x_pre][y] == 0)
{
tmp.push(Point2D(x_pre, y));
}
else
{
return 0;
}
}
}
if (y_pre <= y_las)
{
for (int y = min + 1; y < max; y++)
{
if (data[x_pre][y] == 0)
{
tmp.push(Point2D(x_pre, y));
}
else
{
return 0;
}
}
}
return (max - min); //代表队列多少个数据
}
return 0;
}
int search_1(Point2D pre, Point2D las, queue<Point2D> &tmp)
//1个拐点
{
if (data[las.x][pre.y] == 0)//右下
{
if (search_0(pre, Point2D(las.x, pre.y), tmp) != 0)
{
if (search_0(Point2D(las.x, pre.y), las, tmp) != 0)
{
return tmp.size();
}
}
}
for (; !tmp.empty();)//清空
{
tmp.pop();
}
if (data[pre.x][las.y] == 0)//左上
{
if (search_0(pre, Point2D(pre.x, las.y), tmp) != 0)
{
if (search_0(Point2D(pre.x, las.y), las, tmp) != 0)
{
return tmp.size();
}
}
}
return 0;
}
int search_2(Point2D pre, Point2D las, queue<Point2D> &tmp)
{//2拐点
//凹型y+
for (int i = 0; i < y; i++)
{
for (; !tmp.empty();)//清空
{
tmp.pop();
}
if (data[las.x][las.y + i] == 0)//凹型
{
if (search_1(pre, Point2D(las.x, las.y + i), tmp) != 0)
{
if (search_0(Point2D(las.x, las.y + i), las, tmp) != 0)
{
return tmp.size();
}
}
}
}
for (; tmp.empty() == false;)
{
tmp.pop();
}
//凹型y-
for (int i = 0; i < y; i++)
{
for (; !tmp.empty();)//清空
{
tmp.pop();
}
if (data[las.x][las.y - i] == 0)//凹型
{
if (search_1(pre, Point2D(las.x, las.y - i), tmp) != 0)
{
if (search_0(Point2D(las.x, las.y - i), las, tmp) != 0)
{
return tmp.size();
}
}
}
}
for (; tmp.empty() == false;)
{
tmp.pop();
}
//凹型x+
for (int i = 0; i < x; i++)
{
for (; !tmp.empty();)//清空
{
tmp.pop();
}
if (data[las.x + i][las.y] == 0)//凹型
{
if (search_1(pre, Point2D(las.x + i, las.y), tmp) != 0)
{
if (search_0(Point2D(las.x + i, las.y), las, tmp) != 0)
{
return tmp.size();
}
}
}
}
for (; tmp.empty() == false;)
{
tmp.pop();
}
//凹型x-
for (int i = 0; i < x; i++)
{
for (; !tmp.empty();)//清空
{
tmp.pop();
}
if (data[las.x - i][las.y] == 0)//凹型
{
if (search_1(pre, Point2D(las.x - i, las.y), tmp) != 0)
{
if (search_0(Point2D(las.x - i, las.y), las, tmp) != 0)
{
return tmp.size();
}
}
}
}
return 0;
}
int x;
int y;
searchAlg(int l, int w) :y(l), x(w)
{
}
}