给出我的连连看算法 + 征集更好的算法……（希望可以看见双向BFS的……）
我的算法是基于穷举路径的。说来很吓人，其实速度非常快。因为连连看只允许最多两次转弯，这样最多也只有三条路径。只需要找出这三条就够了。而这三条肯定有两条，使两点在上面。这样其实我们只需要确定一条路径就够了。先确定两个点包括的区域，然后逐行验证是否有可以到达的路径。这就是我的思路。
但是听说BFS（特别是双向BFS）很适合做这种情况。我自己写了下，怎么写怎么觉得麻烦……可能是思维定式吧。我提供自己的核心代码。希望也有高手能给出使用广度优先搜索或者是其他高效的算法。先谢谢了~~
以下的代码，LLKNode其实就是CPoint的typedef。pv是vector<CPoint>的typedef。不知道的人就当它是一个顺序表就可以了。结果用pv返回。返回起始点和结束点还有所有的转折点。（其实最多也就四个点）
cx和cy是游戏盘的最大横竖格子数。因为允许使用盘外来连线，所以点的取值是([-1,cx],[-1,cy])。Loc取棋盘中某个点的状态。NOPAN代表此点没有图片，其余的数字代表图片编号。这里没有使用。
Search代表搜索横竖的连通区域。CheckHLine和CheckVLine用来测试横竖情况下是否连通。两个函数只有很少的区别。Check是调用接口。由用户调用Check，由Check判断点的位置再调用CheckHLine和CheckVLine两个函数。
程序代码：
我的算法是基于穷举路径的。说来很吓人，其实速度非常快。因为连连看只允许最多两次转弯，这样最多也只有三条路径。只需要找出这三条就够了。而这三条肯定有两条，使两点在上面。这样其实我们只需要确定一条路径就够了。先确定两个点包括的区域，然后逐行验证是否有可以到达的路径。这就是我的思路。
但是听说BFS（特别是双向BFS）很适合做这种情况。我自己写了下，怎么写怎么觉得麻烦……可能是思维定式吧。我提供自己的核心代码。希望也有高手能给出使用广度优先搜索或者是其他高效的算法。先谢谢了~~
以下的代码，LLKNode其实就是CPoint的typedef。pv是vector<CPoint>的typedef。不知道的人就当它是一个顺序表就可以了。结果用pv返回。返回起始点和结束点还有所有的转折点。（其实最多也就四个点）
cx和cy是游戏盘的最大横竖格子数。因为允许使用盘外来连线，所以点的取值是([-1,cx],[-1,cy])。Loc取棋盘中某个点的状态。NOPAN代表此点没有图片，其余的数字代表图片编号。这里没有使用。
Search代表搜索横竖的连通区域。CheckHLine和CheckVLine用来测试横竖情况下是否连通。两个函数只有很少的区别。Check是调用接口。由用户调用Check，由Check判断点的位置再调用CheckHLine和CheckVLine两个函数。
程序代码：
int LLKPlane::Search( FX f,LLKNode pbeg,LLKNode& pret ) {
int bc=0;
switch (f) {
case LEFT:
while (--pbeg.x>=-1 && Loc(pbeg) == NOPAN && ++bc)
if (pbeg.x==-1)break;
break;
case RIGHT:
while (++pbeg.x<=cx && Loc(pbeg) == NOPAN && ++bc)
if (pbeg.x==cx)break;
break;
case UP:
while (--pbeg.y>=-1 && Loc(pbeg) == NOPAN && ++bc)
if (pbeg.y==-1)break;
break;
case DOWN:
while (++pbeg.y<=cy && Loc(pbeg) == NOPAN && ++bc)
if (pbeg.y==cy)break;
break;
}
pret=pbeg;
return bc;
}
//检查是否有 "LI" 型的连线，假设p1在左，p2在右
//返回最短路径的长度，如果没有找到路径，返回0
bool LLKPlane::CheckHLine( pv& vec,LLKNode p1,LLKNode p2 ) {
LLKNode pp;
int p1ub,p2ub,p1db,p2db,beg,end;
p1ub=p1.y-Search(UP,p1,pp);
p1db=p1.y+Search(DOWN,p1,pp);
p2ub=p2.y-Search(UP,p2,pp);
p2db=p2.y+Search(DOWN,p2,pp);
//连通域不相交
if (p1ub>p2db || p2ub>p1db)
return false;
//上界，选比较大的
if (p1ub>p2ub) beg=p1ub;
else beg=p2ub;
//下界，选比较小的
if (p1db<p2db) end=p1db;
else end=p2db;
for (int i=beg;i<=end;i++) {
if (Search(RIGHT,LLKNode(p1.x,i),pp)
&& (pp.x > p2.x || pp==p2) ) {
vec.clear();
vec.push_back(p1);
if (i!=p1.y)vec.push_back(LLKNode(p1.x,i));
if (i!=p2.y)vec.push_back(LLKNode(p2.x,i));
vec.push_back(p2);
return true;
}
}
return false;
}
//检查是否有 “匚” 型的连线，假设p1在上，p2在下
//返回最短路径的长度，如果没有找到路径，返回0
bool LLKPlane::CheckVLine( pv& vec,LLKNode p1,LLKNode p2 ) {
LLKNode pp;
int p1lb,p2lb,p1rb,p2rb,beg,end;
p1lb=p1.x-Search(LEFT,p1,pp);
p1rb=p1.x+Search(RIGHT,p1,pp);
p2lb=p2.x-Search(LEFT,p2,pp);
p2rb=p2.x+Search(RIGHT,p2,pp);
//连通域不相交
if (p1lb>p2rb || p2lb>p1rb)
return false;
//上界，选比较大的
if (p1lb>p2lb) beg=p1lb;
else beg=p2lb;
//下界，选比较小的
if (p1rb<p2rb) end=p1rb;
else end=p2rb;
for (int i=beg;i<=end;i++) {
if (Search(DOWN,LLKNode(i,p1.y),pp)
&& (pp.y > p2.y || pp==p2) ) {
vec.clear();
vec.push_back(p1);
if (i!=p1.x)vec.push_back(LLKNode(i,p1.y));
if (i!=p2.x)vec.push_back(LLKNode(i,p2.y));
vec.push_back(p2);
return true;
}
}
return false;
}
bool LLKPlane::Check( LLKNode p1,LLKNode p2,pv& vec ) {
if (p1 == p2 || Loc(p1)!=Loc(p2) || Loc(p1)==NOPAN)
return false;
if (p1.x == p2.x) {
if (abs(p2.y-p1.y) == 1) {
vec.clear();
vec.push_back(p1);
vec.push_back(p2);
return true;
}
if (p1.y > p2.y) //p2在p1上方
return CheckVLine(vec,p2,p1);
else //p2在p1下方
return CheckVLine(vec,p1,p2);
} else if (p1.y == p2.y) {
if (abs(p2.x-p1.x) == 1) {
vec.clear();
vec.push_back(p1);
vec.push_back(p2);
return true;
}
if (p1.x > p2.x) //p2在p1的左边
return CheckHLine(vec,p2,p1);
else //p2在p1的右边
return CheckHLine(vec,p1,p2);
} else {
if (p1.x > p2.x)
if (p1.y > p2.y) //p2在p1的左上
return CheckHLine(vec,p2,p1)
|| CheckVLine(vec,p2,p1);
else//p2在p1的左下
return CheckHLine(vec,p2,p1)
|| CheckVLine(vec,p1,p2);
else
if (p1.y > p2.y) //p2在p1的右上
return CheckHLine(vec,p1,p2)
|| CheckVLine(vec,p2,p1);
else //p2在p1的右下
return CheckHLine(vec,p1,p2)
|| CheckVLine(vec,p1,p2);
}
}
int bc=0;
switch (f) {
case LEFT:
while (--pbeg.x>=-1 && Loc(pbeg) == NOPAN && ++bc)
if (pbeg.x==-1)break;
break;
case RIGHT:
while (++pbeg.x<=cx && Loc(pbeg) == NOPAN && ++bc)
if (pbeg.x==cx)break;
break;
case UP:
while (--pbeg.y>=-1 && Loc(pbeg) == NOPAN && ++bc)
if (pbeg.y==-1)break;
break;
case DOWN:
while (++pbeg.y<=cy && Loc(pbeg) == NOPAN && ++bc)
if (pbeg.y==cy)break;
break;
}
pret=pbeg;
return bc;
}
//检查是否有 "LI" 型的连线，假设p1在左，p2在右
//返回最短路径的长度，如果没有找到路径，返回0
bool LLKPlane::CheckHLine( pv& vec,LLKNode p1,LLKNode p2 ) {
LLKNode pp;
int p1ub,p2ub,p1db,p2db,beg,end;
p1ub=p1.y-Search(UP,p1,pp);
p1db=p1.y+Search(DOWN,p1,pp);
p2ub=p2.y-Search(UP,p2,pp);
p2db=p2.y+Search(DOWN,p2,pp);
//连通域不相交
if (p1ub>p2db || p2ub>p1db)
return false;
//上界，选比较大的
if (p1ub>p2ub) beg=p1ub;
else beg=p2ub;
//下界，选比较小的
if (p1db<p2db) end=p1db;
else end=p2db;
for (int i=beg;i<=end;i++) {
if (Search(RIGHT,LLKNode(p1.x,i),pp)
&& (pp.x > p2.x || pp==p2) ) {
vec.clear();
vec.push_back(p1);
if (i!=p1.y)vec.push_back(LLKNode(p1.x,i));
if (i!=p2.y)vec.push_back(LLKNode(p2.x,i));
vec.push_back(p2);
return true;
}
}
return false;
}
//检查是否有 “匚” 型的连线，假设p1在上，p2在下
//返回最短路径的长度，如果没有找到路径，返回0
bool LLKPlane::CheckVLine( pv& vec,LLKNode p1,LLKNode p2 ) {
LLKNode pp;
int p1lb,p2lb,p1rb,p2rb,beg,end;
p1lb=p1.x-Search(LEFT,p1,pp);
p1rb=p1.x+Search(RIGHT,p1,pp);
p2lb=p2.x-Search(LEFT,p2,pp);
p2rb=p2.x+Search(RIGHT,p2,pp);
//连通域不相交
if (p1lb>p2rb || p2lb>p1rb)
return false;
//上界，选比较大的
if (p1lb>p2lb) beg=p1lb;
else beg=p2lb;
//下界，选比较小的
if (p1rb<p2rb) end=p1rb;
else end=p2rb;
for (int i=beg;i<=end;i++) {
if (Search(DOWN,LLKNode(i,p1.y),pp)
&& (pp.y > p2.y || pp==p2) ) {
vec.clear();
vec.push_back(p1);
if (i!=p1.x)vec.push_back(LLKNode(i,p1.y));
if (i!=p2.x)vec.push_back(LLKNode(i,p2.y));
vec.push_back(p2);
return true;
}
}
return false;
}
bool LLKPlane::Check( LLKNode p1,LLKNode p2,pv& vec ) {
if (p1 == p2 || Loc(p1)!=Loc(p2) || Loc(p1)==NOPAN)
return false;
if (p1.x == p2.x) {
if (abs(p2.y-p1.y) == 1) {
vec.clear();
vec.push_back(p1);
vec.push_back(p2);
return true;
}
if (p1.y > p2.y) //p2在p1上方
return CheckVLine(vec,p2,p1);
else //p2在p1下方
return CheckVLine(vec,p1,p2);
} else if (p1.y == p2.y) {
if (abs(p2.x-p1.x) == 1) {
vec.clear();
vec.push_back(p1);
vec.push_back(p2);
return true;
}
if (p1.x > p2.x) //p2在p1的左边
return CheckHLine(vec,p2,p1);
else //p2在p1的右边
return CheckHLine(vec,p1,p2);
} else {
if (p1.x > p2.x)
if (p1.y > p2.y) //p2在p1的左上
return CheckHLine(vec,p2,p1)
|| CheckVLine(vec,p2,p1);
else//p2在p1的左下
return CheckHLine(vec,p2,p1)
|| CheckVLine(vec,p1,p2);
else
if (p1.y > p2.y) //p2在p1的右上
return CheckHLine(vec,p1,p2)
|| CheckVLine(vec,p2,p1);
else //p2在p1的右下
return CheckHLine(vec,p1,p2)
|| CheckVLine(vec,p1,p2);
}
}
2008-1-2 13:50