如何用C语言实现迷宫出口搜索(人大版)

任务描述:

根据如下的人大校园地图，给出起点、终点，寻找并显示一条通路，或告知通路不存在。

任务提示:

使用Stack数据结构

输入参数

//出题者给的人大校园地图，供参考
//怒问: 明德楼在哪里?
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 1,0,1,1,1,1,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,1,1,1,1,1, 1,0,1,0,0,1,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1, 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,0,1, 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1, 1,0,1,1,0,0,0,0,1,1,1,0,0,0,0,1,0,0,0,1,1,0,1,1,1,0,0,1, 1,0,1,1,0,0,0,0,1,1,1,0,0,0,1,0,0,0,0,1,1,0,1,1,1,1,0,1, 1,0,1,1,0,0,0,0,1,1,1,0,0,1,1,0,0,0,0,1,1,0,1,1,1,1,0,1, 1,0,1,1,0,1,1,1,1,1,1,0,0,0,1,0,0,0,0,1,1,0,1,1,1,0,0,1, 1,0,1,1,0,1,1,1,1,1,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1, 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1, 1,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,1,1,0,1,1,0,1,1,0,0,0,1, 1,0,0,0,1,1,1,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};

C语言实现代码

工作环境: Xcode

#include <stdio.h>
#include <stdlib.h>
#define ERROR -1
#define W 28    //width
#define H 14    //height
#define INITSIZE (100)
#define INCREMENT (20)
/*Maze program V1.0 送检版*/

typedef struct{
    int x;
    int y;
    /*dir 0:east; 1:south: 2:west: 3:north*/
    int dir;
}ElemType;

typedef struct{
    ElemType *base;
    int top;
    int stacksize;
}SqStack ;

void init_stack(SqStack *S) {
    S->base = (ElemType *)malloc(INITSIZE*sizeof(ElemType));
    if (!S) {printf("Out of space.\n"); exit(ERROR);}
    S->top = 0;
    S->stacksize = INITSIZE;
    printf("Stack初始化完成. \n");
}

void push(SqStack *S, ElemType e) {
    if (S->top >= S->stacksize-1) {
        printf("Stack full.\n");
        S->base = (ElemType *)realloc(S->base, (INITSIZE+INCREMENT)*sizeof(ElemType));
    }
    S->base[S->top] = e;
    S->top++;
}

void pop(SqStack *S, ElemType *e) {
    if (S->top == 0) {
        printf("Stack empty.\n");
    }
    *e = S->base[S->top-1];
    S->top--;
}

void print_map(int map[H][W]) {
    int i, j;
    printf("标记: 1代表墙壁,0代表通道,2代表走过的路径.\n");
    printf("Map: \n");
    for (i=0; i<H; i++) {   //i表示行
        for (j=0; j<W; j++) {   //j表示列
            printf("%d ",map[i][j]);
        }
        printf("\n");
    }
}

int find_path(SqStack *S, int map[H][W], ElemType start, ElemType end) {
    /*变量初始化*/
    //1,设置起点为当前点
    ElemType cur = start;
    //2,用count记录走过的步数
    int count = 0;
    /*开始运行*/
    do {
        printf("loop\n");
        count++;
        /*是否终点*/
        if (cur.x==end.x && cur.y==end.y) {
            map[cur.y][cur.x] = 2;
            printf("到达终点, 使用了%d步.\n",count);
            return 0;
        }
        switch (0) {    //switch先从东方向开始探测
            /*东方向*/
            case 0:
                //先写好当前点的方向;
                cur.dir = 0;
                /*可以通行*/
                //需要满足该点本身在图中是0, 而且没有被标记过;
                if (map[cur.y][cur.x+1]==0){
                    /*跳入下一个位置*/
                    //1, 当前点入栈
                    push(S, cur);
                    //1, 修改地图上的当前点当做踩过的点为2
                    map[cur.y][cur.x] = 2;
                    printf("(%d,%d)\n",cur.x,cur.y);
                    //2, 修改当前点
                    cur.x++;
                    break;  //这个break是跳出switch选择;
                }
            /*南方向*/
            case 1:
                //先写好当前点的方向;
                cur.dir = 1;
                /*可以通行*/
                //需要满足该点本身在图中是0, 而且没有被标记过;
                if (map[cur.y+1][cur.x]==0){
                    /*跳入下一个位置*/
                    //1, 当前点入栈
                    push(S, cur);
                    //1, 修改地图上的当前点当做踩过的点为2
                    map[cur.y][cur.x] = 2;
                    printf("(%d,%d)\n",cur.x,cur.y);
                    //2, 修改当前点
                    cur.y++;
                    break;  //这个break是跳出switch选择;
                }
            /*西方向*/
            case 2:
                //先写好当前点的方向;
                cur.dir = 2;
                /*可以通行*/
                //需要满足该点本身在图中是0, 而且没有被标记过;
                if (map[cur.y][cur.x-1]==0){
                    /*跳入下一个位置*/
                    //1, 当前点入栈
                    push(S, cur);
                    //1, 修改地图上的当前点当做踩过的点为2
                    map[cur.y][cur.x] = 2;
                    printf("(%d,%d)\n",cur.x,cur.y);
                    //2, 修改当前点
                    cur.x--;
                    break;  //这个break是跳出switch选择;
                }
            /*北方向*/
            case 3:
                //先写好当前点的方向;
                cur.dir = 3;
                /*可以通行*/
                //需要满足该点本身在图中是0, 而且没有被标记过;
                if (map[cur.y-1][cur.x]==0){
                    /*跳入下一个位置*/
                    //1, 当前点入栈
                    push(S, cur);
                    //1, 修改地图上的当前点当做踩过的点为2
                    map[cur.y][cur.x] = 2;
                    printf("(%d,%d)\n",cur.x,cur.y);
                    //2, 修改当前点
                    cur.y--;
                    break;  //这个break是跳出switch选择;
                }
            /*四个方向都探测不通*/
            default:
                pop(S, &cur);
                printf("(%d,%d)\n",cur.x,cur.y);
                break;
        }
    } while (cur.x!=start.x || cur.y!=start.y);   //当一路退回到了起点,就跳出循环,表示失败了;
    printf("找不到终点.\n");
    return 0;
}

int main()
{
    int map[14][28]=                     //人大校园地图，供参考, W=28, H=14
       {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
        1,0,1,1,1,1,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,1,1,1,1,1,
        1,0,1,0,0,1,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,
        1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,0,1,
        1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,
        1,0,1,1,0,0,0,0,1,1,1,0,0,0,0,1,0,0,0,1,1,0,1,1,1,0,0,1,
        1,0,1,1,0,0,0,0,1,1,1,0,0,0,1,0,0,0,0,1,1,0,1,1,1,1,0,1,
        1,0,1,1,0,0,0,0,1,1,1,0,0,1,1,0,0,0,0,1,1,0,1,1,1,1,0,1,
        1,0,1,1,0,1,1,1,1,1,1,0,0,0,1,0,0,0,0,1,1,0,1,1,1,0,0,1,
        1,0,1,1,0,1,1,1,1,1,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,
        1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,
        1,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,1,1,0,1,1,0,1,1,0,0,0,1,
        1,0,0,0,1,1,1,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,
        1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};
    print_map(map);
    /*变量初始化: start & end 初始化*/
    SqStack S;
    init_stack(&S);
    ElemType start, end;
    start.x = 1; start.y = 1; start.dir = 0;
    end.x = W-1-1; end.y = H-1-1;
    
    find_path(&S,map,start,end);
    print_map(map);
    return 0;
}

/*开发日志*/
//原本我想在ElemType中加入pre, next, 但是实际上是不必要的,用pop就可以得到上一个点
//也就是说,stack结构自然而然能找到上一个, 因此只要在每个元素中写入下个元素的方向就可以了;
//基础操作方法准备完毕;
//17:45第一次测试: bug发现是只循环4次
//23:00去掉了循环以后, 发现只进行一次寻找;
//8:28 代码出现了死循环; 而且当某个点发现不通了,退回上一点的时候, cur是否有把坐标还原到上一点呢? 另外, 还原到上一点以后, 是怎么保证能做继续探索其他方向来找下一点的, 直到都不行才继续往回退?
//8:55 代码运行成功, 最后阻止程序正确执行的原来是我的终点条件的x和y检查写错了, 居然写成cur.x==y而不是cur.x==x!
//8:59 添加了记录步数的count变量, 增加了注释;
//9:06 删除多余注释,程序完成,可以提交.
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 215,133评论 6赞 497
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 91,682评论 3赞 390
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 160,784评论 0赞 350
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 57,508评论 1赞 288
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 66,603评论 6赞 386
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,607评论 1赞 293
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,604评论 3赞 415
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,359评论 0赞 270
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,805评论 1赞 307
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,121评论 2赞 330
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,280评论 1赞 344
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,959评论 5赞 339
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,588评论 3赞 322
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,206评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,442评论 1赞 268
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 47,193评论 2赞 367
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,144评论 2赞 352

推荐阅读更多精彩内容

  • 走过
    走过来，又走过去，一会走到东边，一会又往西去。
    furx阅读 174评论 0赞 2
  • 最美芦花
    最近汉江边，芦苇如雪，美似仙境…… 摄影：宁静致远 ​​​
    陌尘低语阅读 1,640评论 29赞 27
  • 我的蜜蜂情缘
    春天来了，百花即将争艳。看着田野里盛开的油菜花丛中蜜蜂飞舞繁忙，好不热闹啊！ 看着这生机勃勃的景象，我的内心喜悦极...
    吐故纳新_32c8阅读 449评论 3赞 13
  • 爸爸和闺蜜之间有张床
    寄语：我希望每一个姑娘，在人生困境中都能看到希望。寻求亲人的帮助，朋友会给予你力量。 【1】 今天这个故事很难启齿...
    荷乐乐阅读 3,925评论 63赞 30