迷宫问题

C 解法, 执行用时: 1ms, 内存消耗: 348KB, 提交时间: 2021-06-02

#include <stdio.h>
#include <string.h>
struct Info{
    int x, y;
};
typedef struct Info INFO;

char maze[10][10], *p;
INFO record[100];
int N_e, M_e, idx;

char trace(int x, int y)
{
    record[ idx++ ] = (INFO){x, y};
    if(x==N_e && y==M_e){
        for(int i=0; i<idx; i++)
            printf("(%d,%d)\n", record[i].x, record[i].y);
        return 1;
    }
    maze[x][y] = 7;
    
    if(x<N_e && !maze[ x+1 ][y] && trace(x+1, y)) return 1;
    if(y<M_e && !maze[x][ y+1 ] && trace(x, y+1)) return 1;
    if(x && !maze[ x-1 ][y] && trace(x-1, y)) return 1;
    if(y && !maze[x][ y-1 ] && trace(x, y-1)) return 1;
    
    maze[x][y] = 0;   idx--;
    return 0;
}

int main(void)
{
    int N, M;
    while(scanf("%d%d", &N, &M) != EOF)
    {
        N_e = N-1;   M_e = M-1;
        for(int i=0; i<N; i++){
            p = maze[i];
            for(int j=0; j<M; j++)
                scanf("%d", p+j);
        }
        idx = 0;
        trace(0, 0);
    }
    return 0;
}

C 解法, 执行用时: 1ms, 内存消耗: 384KB, 提交时间: 2021-08-02

#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]; }
 
 

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

详情