c++以一个m*n的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍。设计一个程序,对任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论。 要求:首先实现一个栈类型,然后编写一个求解迷宫的非递归

实现一个栈类型：

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

const int MaxSize = 100; // 栈的最大容量

template<class T>
class Stack {
public:
    Stack(); // 构造函数，初始化栈顶指针为-1
    bool isEmpty(); // 判断栈是否为空
    bool isFull(); // 判断栈是否已满
    bool push(T x); // 元素x入栈
    bool pop(T& x); // 栈顶元素出栈，并将其置于x中
    bool getTop(T& x); // 获取栈顶元素，并将其置于x中
    ~Stack(); // 析构函数
private:
    T data[MaxSize]; // 栈元素数组
    int top; // 栈顶指针
};

template<class T>
Stack<T>::Stack() {
    top = -1; // 初始化栈顶指针为-1
}

template<class T>
bool Stack<T>::isEmpty() {
    return top == -1; // 栈为空的条件是栈顶指针为-1
}

template<class T>
bool Stack<T>::isFull() {
    return top == MaxSize - 1; // 栈已满的条件是栈顶指针为MaxSize-1
}

template<class T>
bool Stack<T>::push(T x) {
    if (isFull()) return false; // 栈已满，无法入栈
    data[++top] = x; // 栈顶指针加1，将元素x入栈
    return true;
}

template<class T>
bool Stack<T>::pop(T& x) {
    if (isEmpty()) return false; // 栈为空，无法出栈
    x = data[top--]; // 将栈顶元素置于x中，栈顶指针减1
    return true;
}

template<class T>
bool Stack<T>::getTop(T& x) {
    if (isEmpty()) return false; // 栈为空，无法获取栈顶元素
    x = data[top]; // 获取栈顶元素
    return true;
}

template<class T>
Stack<T>::~Stack() { }

编写一个求解迷宫的非递归算法：

#include<iostream>
using namespace std;

const int MaxSize = 100; // 栈的最大容量
const int MaxRow = 10; // 迷宫行数的最大值
const int MaxCol = 10; // 迷宫列数的最大值

typedef struct {
    int i; // 行下标
    int j; // 列下标
    int di; // 方向
} Box;

// 根据迷宫地图生成迷宫
void generateMaze(int maze[][MaxCol], int row, int col) {
    cout << "请输入迷宫地图，0表示通路，1表示障碍：" << endl;
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            cin >> maze[i][j];
        }
    }
}

// 初始化迷宫路径
void initPath(int path[][MaxCol], int row, int col) {
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            path[i][j] = 0; // 初始化为0，表示未经过
        }
    }
}

// 输出迷宫地图
void printMaze(int maze[][MaxCol], int row, int col) {
    cout << "迷宫地图如下：" << endl;
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            cout << maze[i][j] << " ";
        }
        cout << endl;
    }
}

// 输出迷宫路径
void printPath(int path[][MaxCol], int row, int col) {
    cout << "迷宫路径如下：" << endl;
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            cout << path[i][j] << " ";
        }
        cout << endl;
    }
}

// 判断当前位置是否为迷宫的出口
bool isExit(Box b, int exitRow, int exitCol) {
    return b.i == exitRow && b.j == exitCol;
}

// 判断当前位置是否为迷宫的通路
bool isPath(int maze[][MaxCol], int path[][MaxCol], Box b) {
    return maze[b.i][b.j] == 0 && path[b.i][b.j] == 0;
}

// 将当前位置的四个方向压入栈中
void pushBox(Stack<Box>& s, Box b) {
    Box temp;
    temp.i = b.i - 1; // 上
    temp.j = b.j;
    temp.di = 0;
    if (temp.i >= 0) s.push(temp);
    temp.i = b.i;
    temp.j = b.j + 1; // 右
    temp.di = 1;
    if (temp.j < MaxCol) s.push(temp);
    temp.i = b.i + 1; // 下
    temp.j = b.j;
    temp.di = 2;
    if (temp.i < MaxRow) s.push(temp);
    temp.i = b.i;
    temp.j = b.j - 1; // 左
    temp.di = 3;
    if (temp.j >= 0) s.push(temp);
}

// 非递归求解迷宫
bool findPath(int maze[][MaxCol], int path[][MaxCol], int entryRow, int entryCol, int exitRow, int exitCol) {
    Stack<Box> s; // 定义栈s
    Box b;
    b.i = entryRow;
    b.j = entryCol;
    b.di = -1; // -1表示起点方向
    s.push(b); // 起点进栈
    while (!s.isEmpty()) {
        s.getTop(b); // 获取栈顶元素
        if (isExit(b, exitRow, exitCol)) { // 到达终点
            return true;
        } else if (isPath(maze, path, b)) { // 当前位置是通路
            path[b.i][b.j] = 1; // 标记当前位置已经走过
            Box temp = b; // 备份当前位置
            pushBox(s, b); // 将当前位置的四个方向压入栈中
            if (temp.i == b.i && temp.j == b.j) { // 当前位置的四个方向都没有可行的路径
                s.pop(b); // 弹出当前位置
                path[b.i][b.j] = 0; // 标记当前位置未走过
            }
        } else {
            s.pop(b); // 当前位置不是通路，弹出当前位置
        }
    }
    return false; // 没有找到通路
}

int main() {
    int maze[MaxRow][MaxCol]; // 迷宫地图
    int path[MaxRow][MaxCol]; // 迷宫路径
    int entryRow, entryCol, exitRow, exitCol; // 入口行、入口列、出口行、出口列
    cout << "请输入迷宫的行数和列数：" << endl;
    int row, col;
    cin >> row >> col;
    generateMaze(maze, row, col); // 根据迷宫地图生成迷宫
    initPath(path, row, col); // 初始化迷宫路径
    printMaze(maze, row, col); // 输出迷宫地图
    cout << "请输入迷宫的入口行、入口列、出口行、出口列：" << endl;
    cin >> entryRow >> entryCol >> exitRow >> exitCol;
    if (findPath(maze, path, entryRow, entryCol, exitRow, exitCol)) { // 求解迷宫
        printPath(path, row, col); // 输出迷宫路径
        cout << "存在通路" << endl;
    } else {
        cout << "不存在通路" << endl;
    }
    return 0;
}

输入样例：

请输入迷宫的行数和列数：
5 5
请输入迷宫地图，0表示通路，1表示障碍：
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
迷宫地图如下：
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
请输入迷宫的入口行、入口列、出口行、出口列：
0 0 4 4

输出样例：

迷宫路径如下：
1 0 0 0 0
1 0 0 0 0
1 1 1 1 1
0 0 0 0 1
0 0 0 0 1
存在通路