栈和队列的应用：迷宫问题

我们给出的迷宫如图：

其中，0表示通路，1表示障碍

代码实现如下：

#include <iostream>  
using namespace std;
#include <assert.h>  
#include <stack>  
#include<iomanip>  

const int N = 10;//定义全局变量迷宫的大小（假设迷宫整体为正方形，行列相等）  

struct Pos
{
    int Row;
    int Col;
};

//void GetMaze(int (*maze)[N])//读取迷宫  
//void GetMaze(int **maze)//读取迷宫(需要动态开辟空间)  
//void GetMaze(int maze[][N])//读取迷宫  
void GetMaze(int *maze)//读取迷宫  
{
    FILE* pf = fopen("MazeMap.txt", "r");
    assert(pf);
    char value = 0;
    for (size_t i = 0; i<N; i++)
    {
        for (size_t j = 0; j<N;)
        {
            value = fgetc(pf);
            if (value == '0' || value == '1')
            {
                maze[i*N + j] = value - '0';
                j++;
            }
            else if (value == EOF)
            {
                cout << "maze error!" << endl;
                return;
            }
        }
    }
    fclose(pf);
}
void PrintMaze(int *maze)//打印迷宫  
{
    cout << setw(4);
    for (size_t i = 0; i<N; i++)
    {
        for (size_t j = 0; j<N; j++)
        {
            cout << maze[i*N + j] << setw(4);
        }
        cout << endl;
    }
}
bool CheckIsAccess(int* maze, Pos cur, Pos next)//检查坐标是否合法  
{
    //下一个坐标非法  
    if ((next.Row < 0) || (next.Row >= N)
        || (next.Col < 0) || (next.Col >= N))
    {
        return false;
    }
    //下一个坐标合法  
    if (maze[next.Row*N + next.Col] == 0)
    {
        return true;
    }
    //下一个坐标是以前走过的坐标  
    if (maze[next.Row*N + next.Col] > maze[cur.Row*N + cur.Col] + 1)
    {
        return true;
    }
    return false;
}
void GetMa*Path(int* maze, Pos entry, stack<Pos>& path, stack<Pos>& min)//找通路  
{
    assert(maze);
    path.push(entry);
    Pos cur = entry;
    Pos next = cur;

    //找到通路  

    if (cur.Col == N - 1)
    {
        if (min.empty() || path.size()<min.size())
        {
            min = path;
            //cout<<"找到通路"<<endl;  
        }
        path.pop();
        return;
    }
    //探测上下左右四个方向是否可通  
    //上  
    next = cur;
    next.Row -= 1;
    if (CheckIsAccess(maze, cur, next))
    {
        maze[next.Row*N + next.Col] = maze[cur.Row*N + cur.Col] + 1;
        GetMa*Path(maze, next, path, min);
    }
    //右  
    next = cur;
    next.Col += 1;
    if (CheckIsAccess(maze, cur, next))
    {
        maze[next.Row*N + next.Col] = maze[cur.Row*N + cur.Col] + 1;
        GetMa*Path(maze, next, path, min);
    }
    //下  
    next = cur;
    next.Row += 1;
    if (CheckIsAccess(maze, cur, next))
    {
        maze[next.Row*N + next.Col] = maze[cur.Row*N + cur.Col] + 1;
        GetMa*Path(maze, next, path, min);
    }
    //左  
    next = cur;
    next.Col -= 1;
    if (CheckIsAccess(maze, cur, next))
    {
        maze[next.Row*N + next.Col] = maze[cur.Row*N + cur.Col] + 1;
        GetMa*Path(maze, next, path, min);
    }
    path.pop();
}