1、題目描述

題目鏈接：迷宮問(wèn)題
、

注意不能斜著走！

2、題目分析

（1）0為可以走，1不能走且只有唯一一條通路
（2）我們可以通過(guò)判斷上下左右來(lái)確定路是否能通過(guò)，再設(shè)置如果走過(guò)的路就用 2 來(lái)標(biāo)記，這樣就不會(huì)走回頭路了，如果有多條能通過(guò)，只選擇一條路來(lái)走
（3）當(dāng)我們遇到死胡同時(shí)，應(yīng)該返回到上一個(gè)位置，再重新判斷其他路是否可以走，沒(méi)有就繼續(xù)往回退，直到找到下一條路來(lái)，像這樣的我們就要用到遞歸了。
（4）因?yàn)樽鴺?biāo)是2個(gè)數(shù)據(jù)所以我們創(chuàng)建一個(gè)結(jié)構(gòu)體來(lái)記錄坐標(biāo)。
（5）我們?cè)谝贿M(jìn)到函數(shù)就先保存坐標(biāo)，再找其他的路，如果沒(méi)有找到就說(shuō)明這是一條死胡同，我們就要往后退，再這個(gè)過(guò)程我們還需要將進(jìn)來(lái)保存的坐標(biāo)給拿出來(lái)，這種后進(jìn)先出的的數(shù)據(jù)結(jié)構(gòu)是棧，所以我們要借助棧來(lái)實(shí)現(xiàn)，不懂棧的可以看看哦：棧
（6）因?yàn)闂Ｊ窍冗M(jìn)后出的，所以這跟題目要求不符合，所以我們要再創(chuàng)建一個(gè)棧，將另一個(gè)棧的數(shù)據(jù)倒到新的棧里，再輸出就符合題目要求了
（7）注意：輸出的格式、在結(jié)尾還要釋放棧和創(chuàng)建的數(shù)組、題目可能要求多組測(cè)試用例

3、代碼實(shí)現(xiàn)

#include <stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
//定義結(jié)構(gòu)體，標(biāo)記坐標(biāo)
typedef struct Postion {
    int row;//行
    int col;//列
} PT;
///
//棧
typedef PT STDataType;//結(jié)構(gòu)體類(lèi)型
typedef struct Stack {
    STDataType* a;
    int top;//元素個(gè)數(shù)
    int capacity;//空間大小
} ST;

void StackInit(ST* ps);
void StackDestory(ST* ps);
// 入棧
void StackPush(ST* ps, STDataType x);
// 出棧
void StackPop(ST* ps);
STDataType StackTop(ST* ps);

int StackSize(ST* ps);
bool StackEmpty(ST* ps);

void StackInit(ST* ps) {
    assert(ps);

    ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
    if (ps->a == NULL) {
        printf("malloc fail\n");
        exit(-1);
    }

    ps->capacity = 4;
    ps->top = 0;
}

void StackDestory(ST* ps) {
    assert(ps);
    free(ps->a);
    ps->a = NULL;
    ps->top = ps->capacity = 0;
}

// 入棧
void StackPush(ST* ps, STDataType x) {
    assert(ps);

    // 滿(mǎn)了-》增容
    if (ps->top == ps->capacity) {
        STDataType* tmp = (STDataType*)realloc(ps->a,
            ps->capacity * 2 * sizeof(STDataType));
        if (tmp == NULL) {
            printf("realloc fail\n");
            exit(-1);
        }
        else {
            ps->a = tmp;
            ps->capacity *= 2;
        }
    }

    ps->a[ps->top] = x;
    ps->top++;
}

// 出棧
void StackPop(ST* ps) {
    assert(ps);
    // 棧空了，調(diào)用Pop，直接中止程序報(bào)錯(cuò)
    assert(ps->top > 0);

    //ps->a[ps->top - 1] = 0;
    ps->top--;
}

STDataType StackTop(ST* ps) {
    assert(ps);
    // 棧空了，調(diào)用Top，直接中止程序報(bào)錯(cuò)
    assert(ps->top > 0);

    return ps->a[ps->top - 1];
}

int StackSize(ST* ps) {
    assert(ps);

    return ps->top;
}

bool StackEmpty(ST* ps) {
    assert(ps);

    return ps->top == 0;
}

///
ST Pata;//棧
//判斷是否有路
bool IsPass(int** maze, int N, int M, PT pos) {
    //（1）判斷是否越界
    //（2）判斷坐標(biāo)是否為0
    if (pos.row >= 0 && pos.row < N
        && pos.col >= 0 && pos.col < M
        && maze[pos.row][pos.col] == 0
        ) {
        return true;
    }
    else {
        return false;
    }

}

//打印
void PrintPatar(ST*pata) {
    //再設(shè)置一個(gè)棧
    ST patar;
    StackInit(&patar);
    //將pata這個(gè)棧倒到patar棧里
    while (!StackEmpty(pata)) {
        StackPush(&patar, StackTop(pata));
        StackPop(pata);
    }
    while (!StackEmpty(&patar)) {
        PT top = StackTop(&patar);
        printf("(%d,%d)\n", top.row, top.col);//按照題目的要求打印
        StackPop(&patar);
    }
    //釋放
    StackDestory(&patar);
}

bool GetMazePath(int** maze, int N, int M, PT cur) {
    //先入棧
    StackPush(&Pata, cur);
    //改變當(dāng)前位置
    maze[cur.row][cur.col] = 2;
    //判斷是否到出口
    if (cur.row == N - 1 && cur.col == M - 1)
        return true;
    //接下來(lái)我們分上下左右判斷是否有路可走
    //上
    //記錄上的位置
    PT next = cur;
    next.row -= 1;
    if (IsPass(maze, N, M, next)) {
        //有就進(jìn)行遞歸
        if (GetMazePath(maze, N, M, next))
            //真的有路就返回真即可
            return true;
    }
    //下
     //記錄下的位置
    next = cur;
    next.row += 1;
    if (IsPass(maze, N, M, next)) {
        if (GetMazePath(maze, N, M, next))
            return true;
    }
    //左
     //記錄左的位置
    next = cur;
    next.col -= 1;
    if (IsPass(maze, N, M, next)) {
        if (GetMazePath(maze, N, M, next))
            return true;
    }
    //右
     //記錄右的位置
    next = cur;
    next.col += 1;
    if (IsPass(maze, N, M, next)) {
        if (GetMazePath(maze, N, M, next))
            return true;
    }
    StackPop(&Pata);
    //走到?jīng)]路了就返回假
    return false;
}

int main() {
    int N = 0, M = 0;//行和列的大小
    while (scanf("%d%d", &N, &M) != EOF) {//可能會(huì)有多組測(cè)試用例
        //內(nèi)存函數(shù)造一個(gè)二維數(shù)組
        int** maze = (int**)malloc(sizeof(int*) * N);
        for (int i = 0; i < N; i++)
            maze[i] = (int*)malloc(sizeof(int) * M);
        //輸入迷宮，0代表可過(guò)，1代表不通
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                scanf("%d", &maze[i][j]);
            }
        }
        //初始化，入口
        PT S = { 0, 0 };
        //初始化棧
        StackInit(&Pata);
        //實(shí)行
        GetMazePath(maze, N, M, S);
        //打印
        PrintPatar(&Pata);
        //釋放棧
        StackDestory(&Pata);
        //釋放空間
        for (int i = 0; i < N; i++)
            free(maze[i]);
        free(maze);
        maze = NULL;
    }

    return 0;
}

遞歸過(guò)程：
假設(shè)迷宮：

這就是走整個(gè)迷宮的流程

以上就是我的分享了，如果有什么錯(cuò)誤，歡迎在評(píng)論區(qū)留言。
最后，謝謝大家的觀(guān)看！文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-761174.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)-迷宮問(wèn)題的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！