《连连看》算法c语言演示

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>

//常量习惯定义在程序一开始，以便将来的修改，比如重新定义一个更大的地图界限
//定义图板尺寸
#define _width 20
#define _height 20
//定义数组矩阵中，0表示该格子为空
#define empty (0)
//定义共有20种图片
#define _pics (20)
//定义在图板中随机产生100*2个图片的填充
//使用100是为了每次产生2个相同的图片，从而保证整个图可以消除完
#define _datas (100)
//c语言没有bool类型，为了方便自定义一个
typedef int bool;
#define TRUE (1)
#define FALSE (0)
//定义一个结构用来描述一个点坐标
typedef struct {
    int x;
    int y;
} _point;
//描述图板的数组
int map[_width][_height];

//-------------------------init map----------------------
//从图板中获取一个空白格子的坐标，这种方法随着填充图片的增加，
//效率会急剧降低,不过简单实用，这么小的图板对cpu来说也不算什么
_point getRndEmptyBox(){
    int x,y;
    while(TRUE){
        //gcc的随机数跟windows的随机数产生规则不同
        //linux是产生从0开始到RAND_MAX的一个正整数
        //如果移植到windows,这部分要修改
        int x=rand() % _width;
        int y=rand() % _height;
        if (map[x][y]==empty){
            _point r;
            r.x=x;
            r.y=y;
            return r;
        }
    }
}
//设置一对随机图片
void setRandPic(){
    _point p;
    //+1是为了防止出现随机数为0的情况，那样等于填充了空白
    int pic=rand() % _pics + 1;
    p = getRndEmptyBox();
    map[p.x][p.y]=pic;
    //printf("[%02d,%02d]=%02d\n",p.x,p.y,pic);
    p = getRndEmptyBox();
    map[p.x][p.y]=pic;
    return;
}
//用随机图片填充整个图板
void setRndMap(){
    int i;
    for(i=0;i<_datas;i++){
        setRandPic();
    }
    return;
}
//-----------------------------show status --------------------
//显示当前的图板情况
void dumpMap(){
    int i,j;
    printf("--: ");
    for(i=0;i<_width;i++){
        printf("%02d ",i);
    }
    printf("\n");
    for(i=0;i<_height;i++){
        printf("%02d: ",i);
        for(j=0;j<_width;j++){
            printf("%02d ",map[j][i]);
        }
        printf("\n");
    }
}
//显示当前的图板情况，并且使用红色标注上将要消除的2个点
//显示部分使用了linux的终端控制专用方式，移植到windows时需要修改
void dumpMapWithHotPoint(_point c1,_point c2){
    int x,y;
    //为了方便计数，显示x/y轴格子编号
    printf("--: ");
    for(x=0;x<_width;x++){
        printf("%02d ",x);
    }
    printf("\n");
    for(y=0;y<_height;y++){
        printf("%02d: ",y);
        for(x=0;x<_width;x++){
            if ((c1.x==x && c1.y==y) || (c2.x==x && c2.y==y))
                printf("\e[1;31m%02d\e[0m ",map[x][y]);
            else
                printf("%02d ",map[x][y]);
        }
        printf("\n");
    }
}
//-------------------------search path--------------------
//检查直接连接，返回成功或者失败
bool havePathCorner0(_point p1,_point p2){
    if (p1.x != p2.x && p1.y != p2.y)
        return FALSE; // not in the same line
    int min,max;
    if (p1.x == p2.x){
        min = p1.y < p2.y ? p1.y : p2.y;
        max = p1.y > p2.y ? p1.y : p2.y;
        for(min++;min < max;min++){
            if(map[p1.x][min] != empty)
                return FALSE;  //have block false
        }
    } else {
        min = p1.x < p2.x ? p1.x : p2.x;
        max = p1.x > p2.x ? p1.x : p2.x;
        for(min++;min < max;min++){
            if(map[min][p1.y] != empty)
                return FALSE; //have block false
        }
    }
    return TRUE;
}
//检查1折连接，返回1个点，
//如果点的坐标为负表示不存在1折连接
_point havePathCorner1(_point p1,_point p2){
    _point nullPoint;
    nullPoint.x=nullPoint.y=-1;

    if (p1.x == p2.x || p1.y == p2.y)
        return nullPoint;
    _point c1,c2;
    c1.x=p1.x;
    c1.y=p2.y;
    c2.x=p2.x;
    c2.y=p1.y;
    if (map[c1.x][c1.y] ==  empty){
        bool b1=havePathCorner0(p1,c1);
        bool b2=havePathCorner0(c1,p2);
        if (b1 && b2)
            return c1;
    }
    if (map[c2.x][c2.y] ==  empty){
        bool b1=havePathCorner0(p1,c2);
        bool b2=havePathCorner0(c2,p2);
        if (b1 && b2)
            return c2;
    }
    return nullPoint;
}
//检查两折连接，返回两个点，
//返回点坐标为负表示不存在两折连接
//其中使用了4个方向的循环查找
_point result[2];
_point *havePathCorner2(_point p1,_point p2){
    int i;
    _point *r=result;
    //search direction 1
    for(i=p1.y+1;i<_height;i++){
        if (map[p1.x][i] == empty){
            _point c1;
            c1.x=p1.x;
            c1.y=i;
            _point d1=havePathCorner1(c1,p2);
            if (d1.x != -1){
                r[0].x=c1.x;
                r[0].y=c1.y;
                r[1].x=d1.x;
                r[1].y=d1.y;
                return r;
            }
        } else
        break;
    }
    //search direction 2
    for(i=p1.y-1;i>-1;i--){
        if (map[p1.x][i] == empty){
            _point c1;
            c1.x=p1.x;
            c1.y=i;
            _point d1=havePathCorner1(c1,p2);
            if (d1.x != -1){
                r[0].x=c1.x;
                r[0].y=c1.y;
                r[1].x=d1.x;
                r[1].y=d1.y;
                return r;
            }
        } else
        break;
    }
    //search direction 3
    for(i=p1.x+1;i<_width;i++){
        if (map[i][p1.y] == empty){
            _point c1;
            c1.x=i;
            c1.y=p1.y;
            _point d1=havePathCorner1(c1,p2);
            if (d1.x != -1){
                r[0].x=c1.x;
                r[0].y=c1.y;
                r[1].x=d1.x;
                r[1].y=d1.y;
                return r;
            }
        } else
        break;
    }
    //search direction 4
    for(i=p1.x-1;i>-1;i--){
        if (map[i][p1.y] == empty){
            _point c1;
            c1.x=i;
            c1.y=p1.y;
            _point d1=havePathCorner1(c1,p2);
            if (d1.x != -1){
                r[0].x=c1.x;
                r[0].y=c1.y;
                r[1].x=d1.x;
                r[1].y=d1.y;
                return r;
            }
        } else
        break;
    }
    r[1].x=r[0].x=r[0].y=r[1].y=-1;
    return r;
}
//汇总上面的3种情况，查找两个点之间是否存在合法连接
bool havePath(_point p1,_point p2){
    if (havePathCorner0(p1,p2)){
        printf("[%d,%d] to [%d,%d] have a direct path.\n",p1.x,p1.y,p2.x,p2.y);
        return TRUE;
    } 
    _point r=havePathCorner1(p1,p2);
    if (r.x != -1){
        printf("[%d,%d] to [%d,%d] have a 1 cornor path throught [%d,%d].\n",
            p1.x,p1.y,p2.x,p2.y,r.x,r.y);
        return TRUE;
    } 
    _point *c=havePathCorner2(p1,p2);
    if (c[0].x != -1){
        printf("[%d,%d] to [%d,%d] have a 2 cornor path throught [%d,%d] and [%d,%d].\n",
            p1.x,p1.y,p2.x,p2.y,c[0].x,c[0].y,c[1].x,c[1].y);
        return TRUE;
    } 
    return FALSE;
}
//对于给定的起始点，查找在整个图板中，起始点之后的所有点，
//是否存在相同图片，并且两张图片之间可以合法连线
bool searchMap(_point p1){
    int ix,iy;
    bool inner1=TRUE;

    //printf("begin match:%d,%d\n",p1.x,p1.y);
    int c1=map[p1.x][p1.y];
    for (iy=p1.y;iy<_height;iy++){
        for(ix=0;ix<_width;ix++){
            //遍历查找整个图板的时候，图板中，起始点之前的图片实际已经查找过
            //所以应当从图片之后的部分开始查找才有效率
            //遍历的方式是逐行、每行中逐个遍历
            //在第一次循环的时候，x坐标应当也是起始点的下一个，所以使用inner1来确认第一行循环
            if (inner1){
                ix=p1.x+1;
                inner1=FALSE;
            }
            if(map[ix][iy] != c1){
                //printf("skip:%d,%d\n",ix,iy);
                //continue;
            } else {
                _point p2;
                p2.x=ix;
                p2.y=iy;
                if (!havePath(p1,p2)){
                    //printf("No path from [%d,%d] to [%d,%d]\n",p1.x,p1.y,p2.x,p2.y);
                } else {
                    dumpMapWithHotPoint(p1,p2);
                    map[p1.x][p1.y]=empty;
                    map[p2.x][p2.y]=empty;
                    //dumpMap();
                    return TRUE;
                }
            }
        }
    };
    return FALSE;
}
//这个函数式扫描全图板，自动连连看
bool searchAllMap(){
    int ix,iy;
    bool noPathLeft=FALSE;
    while(!noPathLeft){
        noPathLeft=TRUE;
        for (iy=0;iy<_height;iy++){
            for(ix=0;ix<_width;ix++){
                if(map[ix][iy] != empty){
                    _point p;
                    p.x=ix;
                    p.y=iy;
                    if(searchMap(p) && noPathLeft)
                        noPathLeft=FALSE;
                }
            }
        }
        printf("next loop...\n");
    };
    return TRUE;
}
//-----------------main-----------------------------
int main(int argc,char **argv){
    srand((unsigned)time(NULL));
    memset(map,0,sizeof(map));
    setRndMap();
    dumpMap();
    searchAllMap();
}