连连看两图连通检测算法，折腾了一天总算弄出来了，首先必须要明白我这里的坐标系，如图：
连连看连通方式主要有三种，一种是直线连通，第二种是带一个直角的连通，第三种是带两个直角的连通，其中第三种连通可以化解为第二种连通检测，同理第二种连通可以化解为第一种连通检测，我这里主要讲检测算法，至于图的生成什么的就不多说了，算法用到一些变量说明如下：
//
int BLANK_STATE=-1;//代表空，表示此图已经被消掉
//int W=30;//表示图边长
int m_nCol=10;//表示列数
int m_nRow=12;//表示行数
Point z1;//第一个折点
Point z2;//第二个折点
int *m_map=(int *)malloc(sizeof(int)*m_nCol*m_nRow);
//图片数组，列*行，长度为120，0－9第一行，10－19第二行，
//里面用数字填充，如有12种图，那么就有0-11代表，BLANK_STATE表示此图已经被消掉
//....
//....
//打乱数组m_map
//根据m_map[i]数字内容获取不同图片，根据i按照上图示摆放好不同图片
//...
//...
//按到第一张图，记录下第一张图在数组m_map中的位置t1
//按到第一张图，记录下第二张图在数组m_map中的位置t2
//检测这两张图是否连通
//...
检测两个图是否连通算法如下：
-(BOOL) IsLink:(int)t1 t2:(int)t2 //参数分别为两个图在数组m_map中的位置
{
int x1=t1/m_nCol;//转换为坐标
int y1=t1%m_nCol;
int x2=t2/m_nCol;
int y2=t2%m_nCol;
//水平直连接
if (x1==x2) {
if ([self X_Link:x1 y1:y1 y2:y2]) {
LType=LineType;
CCLOG(@"水平直连接");
return YES;
}
}
//垂直直连接
else if (y1==y2) {
if ([self Y_Link:y1 x1:x1 x2:x2]) {
LType=LineType;
CCLOG(@"垂直直连接");
return YES;
}
}
//一个折点连接
if ([self OneCornerLink:x1 y1:y1 x2:x2 y2:y2]) {
LType=OneCornerType;
CCLOG(@"一个折点连接");
CCLOG(@"折点:x=%i y=%i",z1.v,z1.h);
return YES;
}
//两个折点连接
else if([self TwoCornerLink:x1 y1:y1 x2:x2 y2:y2])
{
LType=TwoCornerType;
CCLOG(@"两个折点连接");
CCLOG(@"折点1:x=%i y=%i",z1.v,z1.h);
CCLOG(@"折点2:x=%i y=%i",z2.v,z2.h);
return YES;
}
return NO;
}
//X直接连通即水平方向连通
-(BOOL) X_Link:(int)x y1:(int)y1 y2:(int)y2
{
if (y1>y2) {
int n=y1;
y1=y2;
y2=n;
}
for (int i=y1+1; i<=y2; i++) {
if (i==y2) {
return YES;
}
if (m_map[x*m_nCol+i]!=BLANK_STATE) {
break;
}
}
return NO;
}
//Y直接连通即垂直方向连通
-(BOOL) Y_Link:(int)y x1:(int)x1 x2:(int)x2
{
if (x1>x2) {
int n=x1;
x1=x2;
x2=n;
}
for (int i=x1+1; i<=x2; i++) {
if (i==x2) {
return YES;
}
if (m_map[i*m_nCol+y]!=BLANK_STATE) {
break;
}
}
return NO;
}
//一个直角接口连通
-(BOOL) OneCornerLink:(int) x1 y1:(int)y1 x2:(int)x2 y2:(int)y2
{
//确保(x1,y1)为矩形下边，(x2,y2)矩形上边，即x1<x2
if (x1>x2) {
int n=x1;
x1=x2;
x2=n;
n=y1;
y1=y2;
y2=n;
}
if (y1<y2) {//(x1,y1)为矩形左下角，(x2,y2)矩形右上角
//判断右下角(x1,y2)是否为空
if (m_map[x1*m_nCol+y2]==BLANK_STATE) {
//判断折点与两个目标点是否连通
if ([self X_Link:x1 y1:y1 y2:y2]&&[self Y_Link:y2 x1:x1 x2:x2]) {
//保存折点坐标
z1.v=x1;
z1.h=y2;
point1=x1*m_nCol+y2;
return YES;
}
}
//判断左上角(x2,y1)是否为空
if (m_map[x2*m_nCol+y1]==BLANK_STATE) {
//判断折点与两个目标点是否连通
if ([self X_Link:x2 y1:y1 y2:y2]&&[self Y_Link:y1 x1:x1 x2:x2]) {
//保存折点坐标
z1.v=x2;
z1.h=y1;
point1=x2*m_nCol+y1;
return YES;
}
}
return NO;
}
else //(x1,y1)为矩形右下角，(x2,y2)矩形左上角
{
//判断左下角(x1,y2)是否为空
if (m_map[x1*m_nCol+y2]==BLANK_STATE) {
//判断折点与两个目标点是否连通
if ([self X_Link:x1 y1:y1 y2:y2]&&[self Y_Link:y2 x1:x1 x2:x2]) {
//保存折点坐标
z1.v=x1;
z1.h=y2;
point1=x1*m_nCol+y2;
return YES;
}
}
//判断右上角(x2,y1)是否为空
if (m_map[x2*m_nCol+y1]==BLANK_STATE) {
//判断折点与两个目标点是否连通
if ([self X_Link:x2 y1:y1 y2:y2]&&[self Y_Link:y1 x1:x1 x2:x2]) {
//保存折点坐标
z1.v=x2;
z1.h=y1;
point1=x2*m_nCol+y1;
return YES;
}
}
return NO;
}
}
//两个直角连通
-(BOOL) TwoCornerLink:(int) x1 y1:(int)y1 x2:(int)x2 y2:(int)y2
{
//确保(x1,y1)为矩形下边，(x2,y2)矩形上边，即x1<x2
if (x1>x2) {
int n=x1;
x1=x2;
x2=n;
n=y1;
y1=y2;
y2=n;
}
int x,y;
//往上
for (x=x1+1; x<=m_nRow; x++) {
//
if (x==m_nRow) {
//
if ([self YThrough:x2+1 y:y2 bAdd:YES]) {
//两个折点都在选中方块上方，且都在图案区域外部
z1.v=m_nRow;
z1.h=y2;/////////////////////////////////////////////////////////////??
z2.v=m_nRow;
z2.h=y1;
return YES;
}
else
{
break;
}
}
if (m_map[x*m_nCol+y1]!=BLANK_STATE) {
break;
}
if ([self OneCornerLink:x y1:y1 x2:x2 y2:y2]) {
z2.v=x;
z2.h=y1;
return YES;
}
}
//往下
for (x=x1-1; x>=-1; x--) {
if (x==-1) {
//
if ([self YThrough:x2-1 y:y2 bAdd:NO]) {
//两个折点都在选中方块下方，且都在图案区域外部
z1.v=-1;
z1.h=y2;/////////////////////////////////////////////////////////////??
z2.v=-1;
z2.h=y1;
return YES;
}
else
{
break;
}
}
if (m_map[x*m_nCol+y1]!=BLANK_STATE) {
break;
}
if ([self OneCornerLink:x y1:y1 x2:x2 y2:y2]) {
z2.v=x;
z2.h=y1;
return YES;
}
}
//往左
for (y=y1-1; y>=-1; y--) {
//
if (y==-1) {
//两个折点都在选中方块左方，且都在图案区域外部
if ([self XThrough:x2 y:y2-1 bAdd:NO]) {
//两个折点都在选中方块左方，且都在图案区域外部
z1.v=x2;/////////////////////////////////////////////////////////////??
z1.h=-1;
z2.v=x1;
z2.h=-1;
return YES;
}
else
{
break;
}
}
if (m_map[x1*m_nCol+y]!=BLANK_STATE) {
break;
}
if ([self OneCornerLink:x1 y1:y x2:x2 y2:y2]) {
//
z2.v=x1;
z2.h=y;
return YES;
}
}
//往右
for (y=y1+1; y<=m_nCol; y++) {
//
if (y==m_nCol) {
//
if ([self XThrough:x2 y:y2+1 bAdd:YES]) {
//两个折点都在选中方块右方，且都在图案区域外部
z1.v=x2;/////////////////////////////////////////////////////////////??
z1.h=m_nCol;
z2.v=x1;
z2.h=m_nCol;
return YES;
}
else
{
break;
}
}
if (m_map[x1*m_nCol+y]!=BLANK_STATE) {
break;
}
if ([self OneCornerLink:x1 y1:y x2:x2 y2:y2]) {
//
z2.v=x1;
z2.h=y;
return YES;
}
}
return NO;
}
//水平连通判断，主要用于判断是否连通边界
-(BOOL) XThrough:(int)x y:(int)y bAdd:(BOOL)bAdd
{
if (bAdd) {
//水平往右是否连通
for (int i=y; i<m_nCol; i++) {
if (m_map[x*m_nCol+i]!=BLANK_STATE) {
return NO;
}
}
}
else
{
//水平往左是否连通
for (int i=0; i<=y; i++) {
if (m_map[x*m_nCol+i]!=BLANK_STATE) {
return NO;
}
}
}
return YES;
}
//垂直连通判断，主要用于判断是否连通边界
-(BOOL) YThrough:(int)x y:(int)y bAdd:(BOOL)bAdd
{
if (bAdd) {
//垂直往上是否连通
for (int i=x; i<m_nRow; i++) {
if (m_map[i*m_nCol+y]!=BLANK_STATE) {
return NO;
}
}
}
else
{
//垂直往下是否连通
for (int i=0; i<=x; i++) {
if (m_map[i*m_nCol+y]!=BLANK_STATE) {
return NO;
}
}
}
return YES;
}
不知道有没有其他更好的办法，欢饮拍砖交流！