栈的应用----走出迷宫

走出迷宫

#define _CRT_SECURE_N0_WARNINGS 1

//规定 上3下1左2右4

#include <iostream>
#include <stack>
using namespace std;

#define ROWSIZE 10
#define COLSIZE 10

typedef int MazeType[ROWSIZE][COLSIZE];

void PrintMaze(MazeType maze)
{
    for (int i = 0; i < ROWSIZE; i++)
    {
        for (int j = 0; j < COLSIZE; j++)
            printf("%d ", maze[i][j]);
        printf("\n");
    }
}

typedef struct{
    int row;
    int col;
}PosType;

typedef struct{
    int ord;//步数
    PosType seat;//位置 
    int di;//1 2 3 4 方向
}SelemType;

bool Is_Pass(MazeType maze, PosType pos)
{
    return maze[pos.row][pos.col] == 0;
}

void FootPrint(MazeType maze, PosType pos)
{
    maze[pos.row][pos.col] = 8;
}

void MarkPrint(MazeType maze, PosType pos)
{
    maze[pos.row][pos.col] = 4;
}

PosType NextPos(PosType pos, int di)
{
    switch (di)
    {
    case 1:
        pos.row += 1;
        break;
    case 2:
        pos.col -= 1;
        break;
    case 3:
        pos.row -= 1;
        break;
    case 4:
        pos.col += 1;
        break;
    default:
        break;
    }
    return pos;
}

void MazePath(MazeType maze,PosType begin, PosType end)
{
    PosType pos = begin;
    int step = 0;
    SelemType e;
    stack <SelemType> st;
    
    do{
        if (Is_Pass(maze, pos))
        {
            e.ord = ++step;
            e.seat = pos;
            e.di = 1;

            FootPrint(maze, pos);
            if (pos.row == end.row && pos.col == end.col)
                break;
            st.push(e);
            pos = NextPos(pos, 1);
        }
        else
        {
            if (!st.empty())
            {
                e=st.top(); st.pop();
                while (e.di == 4 && !st.empty())
                {
                    MarkPrint(maze, e.seat);
                    e=st.top();
                    st.pop();
                }
                if (e.di < 4)
                {
                    e.di++;
                    st.push(e);
                    pos = NextPos(e.seat, e.di);
                }
            }
        }

    } while (!st.empty());

}

int main()
{
    MazeType maze= {
        { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
        { 1, 0, 0, 1, 0, 0, 0, 1, 0, 1 },
        { 1, 0, 0, 1, 0, 0, 0, 1, 0, 1 },
        { 1, 0, 0, 0, 0, 1, 1, 0, 0, 1 },
        { 1, 0, 1, 1, 1, 0, 0, 0, 0, 1 },
        { 1, 0, 0, 0, 1, 0, 0, 0, 0, 1 },
        { 1, 0, 1, 0, 0, 0, 1, 0, 0, 1 },
        { 1, 0, 1, 1, 1, 0, 1, 1, 0, 1 },
        { 1, 1, 0, 0, 0, 0, 0, 0, 0, 1 },
        { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
    };
    PosType begin = {1,1};
    PosType end = {8,8};

    PrintMaze(maze);
    MazePath(maze,begin,end);
    printf("-----------------------------\n");
    PrintMaze(maze);

    return 0;
}

运行结果： image.png