迷宫问题

华为机试练习：迷宫问题
利用回溯法进行深度遍历

C代码：

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

static int N=1, M=1, SIZE=1; // 迷宫尺寸

/* 当前行 */
int row(int idx){ return idx/M; }

/* 当前列 */
int col(int idx){ return idx%M; }


/* 是否可以向上移动 */
int hasUP(int* list, int idx){ return row(idx)>0 && 0==list[idx-M]; }

/* 是否可以向左移动 */
int hasLeft(int* list, int idx){ return col(idx)>0 && 0==list[idx-1]; }

/* 是否可以向下移动 */
int hasDown(int* list, int idx){ return row(idx)<N-1 && 0==list[idx+M]; }

/* 是否可以向右移动 */
int hasRight(int* list, int idx){ return col(idx)<M-1 && 0==list[idx+1]; }


/** 输出解迷宫路径
 *    list: 存储迷宫地图的列表 */
void maze(int* list){
    // 初始化
    int bufSize = SIZE+1, idx=0, cnt=0;
    int* buf = (int*)malloc(bufSize * sizeof(int));

    // 未走过：0，走过：-1，死路：1.
    buf[0] = 0; list[0] = -1;
    while(buf[cnt] < SIZE-1){
        // 判断当前位置
        idx = buf[cnt];
        list[idx] = -1;
        if(!hasUP(list, idx) && !hasLeft(list, idx) &&
           !hasDown(list, idx) && !hasRight(list, idx)){
            // 标记死路并原路返回
            cnt--;
            list[idx] = 1;
            continue;
        }

        // 获取下一位置，加入缓冲区
        if(hasUP(list, idx))
            buf[++cnt] = idx-M;
        if(hasLeft(list, idx))
            buf[++cnt]=idx-1;
        if(hasDown(list, idx))
            buf[++cnt]=idx+M;
        if(hasRight(list, idx))
            buf[++cnt]=idx+1;
        // 后续会依照：→ ↓ ← ↑ 的方向顺序进行搜索
    }
    list[SIZE-1] = -1;    // 到达终点

    // 输出路径
    for(int i=0; i<=cnt; i++){
        idx = buf[i];
        if(list[idx]==-1){
            // 输出已路过位置
            printf("(%d,%d)\n", row(idx), col(idx));
        }
    }
}

/* Main */
int main(){
    // 数据读入
    while(scanf("%d %d", &N, &M)!=EOF){
        SIZE = N*M;
        int* list = (int*)malloc(SIZE * sizeof(int));
        for(int i = 0; i<SIZE; i++){
            scanf("%d", &list[i]);
        }
        // 输出解迷宫路径
        maze(list);
        free(list);
    }
    return 0;
}