首页 » 技术分享 » 连连看两图连通检测算法（Objective-c）

连连看两图连通检测算法（Objective-c）

　
评论关闭　1,066次浏览

连连看两图连通检测算法，折腾了一天总算弄出来了，首先必须要明白我这里的坐标系，如图：

连连看连通方式主要有三种，一种是直线连通，第二种是带一个直角的连通，第三种是带两个直角的连通，其中第三种连通可以化解为第二种连通检测，同理第二种连通可以化解为第一种连通检测，我这里主要讲检测算法，至于图的生成什么的就不多说了，算法用到一些变量说明如下：

    //
    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;
}

不知道有没有其他更好的办法，欢饮拍砖交流！

转载自原文链接, 如需删除请联系管理员。

原文链接：连连看两图连通检测算法（Objective-c），转载请注明来源！

赞 0