迷宫问题--C语言实现

/************************************************************************
 *
 *                            迷宫问题的另类解法
 * 使用递归求解
 * 迷宫问题是堆栈的一个很典型的应用，通常是将走过的路径压到堆栈中。
 * 本程序利用迷宫地图数据来保存路径信息，相对压栈方法节省内存。前提是迷宫地图数据必须是可写的，
 * 实际上迷宫地图可能是只读的，这样的话本程序的方法不可行。
 ************************************************************************/

#include
#include

#define true    1
#define false    0

typedef enum {
    blocked = 0,    //墙位置
    blank,          //没走过的空白位置
    routing,        //已经在路径栈中的位置
    dead            //已经判断为走不通的位置
}m_pos_status;

#define X_LEN    10
#define Y_LEN    10

/* 定义迷宫入口位置 */
#define START_X    1
#define START_Y    0

/* 定义迷宫出口位置 */
#define END_X    9
#define END_Y    8

/* 迷宫图数据出自严蔚敏版《数据结构》图3.4
 * 修改入口位置为<0,1>，出口位置为<8,9>。
 * 坐标格式为
 */
static m_pos_status maze_pos[Y_LEN][X_LEN] = {
        /*0*/                                        /*5*/
   
/*0*/    {blocked,blank,blocked,blocked,blocked,        blocked,blocked,blocked,blocked,blocked},
/*1*/    {blocked,blank,blank,blocked,blank,            blank,blank,blocked,blank,blocked},
/*2*/    {blocked,blank,blank,blocked,blank,            blank,blank,blocked,blank,blocked},
/*3*/    {blocked,blank,blank,blank,blank,            blocked,blocked,blank,blank,blocked},
/*4*/    {blocked,blank,blocked,blocked,blocked,        blank,blank,blank,blank,blocked},
/*5*/    {blocked,blank,blank,blank,blocked,            blank,blank,blank,blank,blocked},
/*6*/    {blocked,blank,blocked,blank,blank,            blank,blocked,blank,blank,blocked},
/*7*/    {blocked,blank,blocked,blocked,blocked,        blank,blocked,blocked,blank,blocked},
/*8*/    {blocked,blocked,blank,blank,blank,            blank,blank,blank,blank,blank},
/*9*/    {blocked,blocked,blocked,blocked,blocked,    blocked,blocked,blocked,blocked,blocked}
};

static int is_valid_pos(int x, int y){
   
    if ( (x == X_LEN ) || (y == Y_LEN) ){
        printf("parameter flow!");
        exit(1);
    }

    switch(maze_pos[y][x]) {
    case blocked:
    case routing:
    case dead:
        return false;

    case blank:
        return true;
        break;
    }

    return false;    /* avoid warning */
}

/* 查看出口是否在当前位置的四周 */
static int check_near_end(int x, int y){

    if ( ((x == END_X) && (y == END_Y))
        || (((x+1) == END_X) && (y == END_Y))
        || (((x-1) == END_X) && (y == END_Y))
        || ((x == END_X) && ((y+1) == END_Y))
        || ((x == END_X) && ((y-1) == END_Y))
        ){
        /* 找到迷宫出口 */
        return true;
    }

    return false;
}

/* 打印入口到出口的路径点，不按顺序 */
static void print_path(void){

    int x;
    int y;

    printf("\n");
    for (y = 0; y < Y_LEN; y++) {
        for (x = 0; x < X_LEN; x++) {
            if (maze_pos[y][x] == routing) {
                printf("(%d,%d)\n",y,x);
            }
        }
    }
}

static int route_pos(int x, int y){
   
    /* 查看出口是否在当前位置的四周 */
    if (check_near_end(x,y)) {
        maze_pos[y][x] = routing;
        print_path();
        printf("press any key to continue...\n");
        getchar();
        /*
        递归层次很可能已经很深，完全退出递归可能要费些时间。
        这里做直接退出进程出来。或者使用longjmp()返回调用主调函数也行。*/
        exit(0);
        return true;
    }

    //try east
    if (x+1 < X_LEN) {
        if (is_valid_pos(x+1,y)) {
            maze_pos[y][x] = routing;
            if (route_pos(x+1,y)) {
                return true;
            }
        }
    }

    //try south
    if (y+1 < Y_LEN) {
        if (is_valid_pos(x,y+1)) {
            maze_pos[y][x] = routing;
            if (route_pos(x,y+1)) {
                return true;
            }
        }
    }

    //try west
    if (x > 1) {
        if (is_valid_pos(x-1,y)) {
            maze_pos[y][x] = routing;
            if (route_pos(x-1,y)) {
                return true;
            }
        }
    }

    //try north
    if (y > 1) {
        if (is_valid_pos(x,y-1)) {
            maze_pos[y][x] = routing;
            if (route_pos(x,y-1)) {
                return true;
            }
        }
    }
   
    maze_pos[y][x] = dead;

    return false;
}

void maze_path(void){

    route_pos(START_X,START_Y);

    return;
}