如何用C語(yǔ)言實(shí)現(xiàn)迷宮出口搜索(人大版)

任務(wù)描述:

根據(jù)如下的人大校園地圖碧信，給出起點(diǎn)、終點(diǎn)韩肝，尋找并顯示一條通路，或告知通路不存在九榔。

任務(wù)提示:

使用Stack數(shù)據(jù)結(jié)構(gòu)

輸入?yún)?shù)

//出題者給的人大校園地圖哀峻，供參考
//怒問: 明德樓在哪里?
{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語(yǔ)言實(shí)現(xiàn)代碼

工作環(huán)境: 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("標(biāo)記: 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,設(shè)置起點(diǎn)為當(dāng)前點(diǎn)
    ElemType cur = start;
    //2,用count記錄走過的步數(shù)
    int count = 0;
    /*開始運(yùn)行*/
    do {
        printf("loop\n");
        count++;
        /*是否終點(diǎn)*/
        if (cur.x==end.x && cur.y==end.y) {
            map[cur.y][cur.x] = 2;
            printf("到達(dá)終點(diǎn), 使用了%d步.\n",count);
            return 0;
        }
        switch (0) {    //switch先從東方向開始探測(cè)
            /*東方向*/
            case 0:
                //先寫好當(dāng)前點(diǎn)的方向;
                cur.dir = 0;
                /*可以通行*/
                //需要滿足該點(diǎn)本身在圖中是0, 而且沒有被標(biāo)記過;
                if (map[cur.y][cur.x+1]==0){
                    /*跳入下一個(gè)位置*/
                    //1, 當(dāng)前點(diǎn)入棧
                    push(S, cur);
                    //1, 修改地圖上的當(dāng)前點(diǎn)當(dāng)做踩過的點(diǎn)為2
                    map[cur.y][cur.x] = 2;
                    printf("(%d,%d)\n",cur.x,cur.y);
                    //2, 修改當(dāng)前點(diǎn)
                    cur.x++;
                    break;  //這個(gè)break是跳出switch選擇;
                }
            /*南方向*/
            case 1:
                //先寫好當(dāng)前點(diǎn)的方向;
                cur.dir = 1;
                /*可以通行*/
                //需要滿足該點(diǎn)本身在圖中是0, 而且沒有被標(biāo)記過;
                if (map[cur.y+1][cur.x]==0){
                    /*跳入下一個(gè)位置*/
                    //1, 當(dāng)前點(diǎn)入棧
                    push(S, cur);
                    //1, 修改地圖上的當(dāng)前點(diǎn)當(dāng)做踩過的點(diǎn)為2
                    map[cur.y][cur.x] = 2;
                    printf("(%d,%d)\n",cur.x,cur.y);
                    //2, 修改當(dāng)前點(diǎn)
                    cur.y++;
                    break;  //這個(gè)break是跳出switch選擇;
                }
            /*西方向*/
            case 2:
                //先寫好當(dāng)前點(diǎn)的方向;
                cur.dir = 2;
                /*可以通行*/
                //需要滿足該點(diǎn)本身在圖中是0, 而且沒有被標(biāo)記過;
                if (map[cur.y][cur.x-1]==0){
                    /*跳入下一個(gè)位置*/
                    //1, 當(dāng)前點(diǎn)入棧
                    push(S, cur);
                    //1, 修改地圖上的當(dāng)前點(diǎn)當(dāng)做踩過的點(diǎn)為2
                    map[cur.y][cur.x] = 2;
                    printf("(%d,%d)\n",cur.x,cur.y);
                    //2, 修改當(dāng)前點(diǎn)
                    cur.x--;
                    break;  //這個(gè)break是跳出switch選擇;
                }
            /*北方向*/
            case 3:
                //先寫好當(dāng)前點(diǎn)的方向;
                cur.dir = 3;
                /*可以通行*/
                //需要滿足該點(diǎn)本身在圖中是0, 而且沒有被標(biāo)記過;
                if (map[cur.y-1][cur.x]==0){
                    /*跳入下一個(gè)位置*/
                    //1, 當(dāng)前點(diǎn)入棧
                    push(S, cur);
                    //1, 修改地圖上的當(dāng)前點(diǎn)當(dāng)做踩過的點(diǎn)為2
                    map[cur.y][cur.x] = 2;
                    printf("(%d,%d)\n",cur.x,cur.y);
                    //2, 修改當(dāng)前點(diǎn)
                    cur.y--;
                    break;  //這個(gè)break是跳出switch選擇;
                }
            /*四個(gè)方向都探測(cè)不通*/
            default:
                pop(S, &cur);
                printf("(%d,%d)\n",cur.x,cur.y);
                break;
        }
    } while (cur.x!=start.x || cur.y!=start.y);   //當(dāng)一路退回到了起點(diǎn),就跳出循環(huán),表示失敗了;
    printf("找不到終點(diǎn).\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;
}

/*開發(fā)日志*/
//原本我想在ElemType中加入pre, next, 但是實(shí)際上是不必要的,用pop就可以得到上一個(gè)點(diǎn)
//也就是說(shuō),stack結(jié)構(gòu)自然而然能找到上一個(gè), 因此只要在每個(gè)元素中寫入下個(gè)元素的方向就可以了;
//基礎(chǔ)操作方法準(zhǔn)備完畢;
//17:45第一次測(cè)試: bug發(fā)現(xiàn)是只循環(huán)4次
//23:00去掉了循環(huán)以后, 發(fā)現(xiàn)只進(jìn)行一次尋找;
//8:28 代碼出現(xiàn)了死循環(huán); 而且當(dāng)某個(gè)點(diǎn)發(fā)現(xiàn)不通了,退回上一點(diǎn)的時(shí)候, cur是否有把坐標(biāo)還原到上一點(diǎn)呢? 另外, 還原到上一點(diǎn)以后, 是怎么保證能做繼續(xù)探索其他方向來(lái)找下一點(diǎn)的, 直到都不行才繼續(xù)往回退?
//8:55 代碼運(yùn)行成功, 最后阻止程序正確執(zhí)行的原來(lái)是我的終點(diǎn)條件的x和y檢查寫錯(cuò)了, 居然寫成cur.x==y而不是cur.x==x!
//8:59 添加了記錄步數(shù)的count變量, 增加了注釋;
//9:06 刪除多余注釋,程序完成,可以提交.
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 人面猴
    序言：七十年代末，一起剝皮案震驚了整個(gè)濱河市剩蟀，隨后出現(xiàn)的幾起案子催蝗，更是在濱河造成了極大的恐慌，老刑警劉巖育特，帶你破解...
    沈念sama閱讀 218,284評(píng)論 6贊 506
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件丙号，死亡現(xiàn)場(chǎng)離奇詭異，居然都是意外死亡缰冤，警方通過查閱死者的電腦和手機(jī)犬缨，發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 93,115評(píng)論 3贊 395
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)棉浸，“玉大人怀薛，你說(shuō)我怎么就攤上這事∶灾＃” “怎么了枝恋？”我有些...
    開封第一講書人閱讀 164,614評(píng)論 0贊 354
  • 道士緝兇錄：失蹤的賣姜人
    文/不壞的土叔 我叫張陵，是天一觀的道長(zhǎng)嗡害。 經(jīng)常有香客問我焚碌，道長(zhǎng)，這世上最難降的妖魔是什么霸妹？ 我笑而不...
    開封第一講書人閱讀 58,671評(píng)論 1贊 293
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任呐能，我火速辦了婚禮，結(jié)果婚禮上抑堡，老公的妹妹穿的比我還像新娘摆出。我一直安慰自己，他們只是感情好首妖，可當(dāng)我...
    茶點(diǎn)故事閱讀 67,699評(píng)論 6贊 392
  • 惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
    文/花漫 我一把揭開白布偎漫。 她就那樣靜靜地躺著，像睡著了一般有缆。 火紅的嫁衣襯著肌膚如雪象踊。 梳的紋絲不亂的頭發(fā)上，一...
    開封第一講書人閱讀 51,562評(píng)論 1贊 305
  • 城市分裂傳說(shuō)
    那天棚壁，我揣著相機(jī)與錄音杯矩，去河邊找鬼。 笑死袖外，一個(gè)胖子當(dāng)著我的面吹牛史隆，可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播曼验，決...
    沈念sama閱讀 40,309評(píng)論 3贊 418
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開眼泌射，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼粘姜！你這毒婦竟也來(lái)了？” 一聲冷哼從身側(cè)響起熔酷，我...
    開封第一講書人閱讀 39,223評(píng)論 0贊 276
  • 萬(wàn)榮殺人案實(shí)錄
    序言：老撾萬(wàn)榮一對(duì)情侶失蹤孤紧，失蹤者是張志新（化名）和其女友劉穎，沒想到半個(gè)月后拒秘，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體号显，經(jīng)...
    沈念sama閱讀 45,668評(píng)論 1贊 314
  • ?護(hù)林員之死
    正文 獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,859評(píng)論 3贊 336
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年躺酒，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了押蚤。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 39,981評(píng)論 1贊 348
  • 活死人
    序言：一個(gè)原本活蹦亂跳的男人離奇死亡阴颖，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出丐膝，到底是詐尸還是另有隱情量愧，我是刑警寧澤，帶...
    沈念sama閱讀 35,705評(píng)論 5贊 347
  • ?日本核電站爆炸內(nèi)幕
    正文 年R本政府宣布帅矗，位于F島的核電站偎肃，受9級(jí)特大地震影響，放射性物質(zhì)發(fā)生泄漏浑此。R本人自食惡果不足惜累颂，卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,310評(píng)論 3贊 330
  • 男人毒藥：我在死后第九天來(lái)索命
    文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望凛俱。 院中可真熱鬧紊馏，春花似錦、人聲如沸蒲犬。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,904評(píng)論 0贊 22
  • 一樁弒父案，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)原叮。三九已至赫编，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間奋隶，已是汗流浹背擂送。 一陣腳步聲響...
    開封第一講書人閱讀 33,023評(píng)論 1贊 270
  • 情欲美人皮
    我被黑心中介騙來(lái)泰國(guó)打工， 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留唯欣，地道東北人嘹吨。 一個(gè)月前我還...
    沈念sama閱讀 48,146評(píng)論 3贊 370
  • 代替公主和親
    正文 我出身青樓，卻偏偏與公主長(zhǎng)得像境氢，于是被迫代替她去往敵國(guó)和親躺苦。 傳聞我的和親對(duì)象是個(gè)殘疾皇子身腻，可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,933評(píng)論 2贊 355

推薦閱讀更多精彩內(nèi)容

  • 走過來(lái)，又走過去匹厘，一會(huì)走到東邊嘀趟，一會(huì)又往西去。
    furx閱讀 175評(píng)論 0贊 2
  • 最近漢江邊愈诚，蘆葦如雪她按，美似仙境…… 攝影：寧?kù)o致遠(yuǎn) ???
    陌塵低語(yǔ)閱讀 1,644評(píng)論 29贊 27
  • 春天來(lái)了，百花即將爭(zhēng)艷炕柔∽锰看著田野里盛開的油菜花叢中蜜蜂飛舞繁忙，好不熱鬧柏袄邸陵刹！ 看著這生機(jī)勃勃的景象，我的內(nèi)心喜悅極...
    吐故納新_32c8閱讀 450評(píng)論 3贊 13
  • 寄語(yǔ)：我希望每一個(gè)姑娘欢嘿，在人生困境中都能看到希望衰琐。尋求親人的幫助，朋友會(huì)給予你力量炼蹦。 【1】 今天這個(gè)故事很難啟齒...
    荷樂樂閱讀 3,934評(píng)論 63贊 30