运用C++栈，链表等基础知识编写一个可运行的迷宫

Question

1．1 问题描述：
迷宫求解是实验心理学中的一个经典问题。从一个入口处进入迷宫，在迷宫中设置很多的障碍，前进的方向有上、下、左、右，有一个唯一的出口。给出在迷宫中寻找通路到达出口的过程。
1．2 基本要求：
1．2．1 设计数据结构存储迷宫
1．2．2 设计存储结构存储从入口到出口的通路
1．2．3 设计算法完成迷宫的求解
1．2．4 分析算法的时间复杂度
运用C++栈，链表等基础知识编写一个可运行的迷宫，这是数据结构的一知识
迷宫图大致为从左上角走到又下角，开始可以用顺时针走。

Answer 1

该回答引用ChatGPT

以下是一个基于C++栈和链表的迷宫求解程序。程序使用矩阵表示迷宫，0表示通路，1表示障碍物。程序使用深度优先搜索算法，在搜索过程中使用栈来存储已经访问过的节点，使用链表来记录路径。在找到终点后，程序输出路径，并释放所有动态分配的内存。

时间复杂度分析：每个节点最多访问一次，因此时间复杂度为O(n)，其中n为节点数。

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

// 迷宫大小
const int ROW = 8;
const int COL = 8;

// 迷宫矩阵
int maze[ROW][COL] = {
    {0, 0, 0, 0, 0, 0, 0, 1},
    {0, 1, 1, 0, 1, 1, 0, 1},
    {0, 0, 0, 1, 0, 0, 0, 1},
    {0, 1, 0, 0, 1, 1, 0, 0},
    {0, 1, 1, 1, 0, 0, 1, 1},
    {0, 1, 0, 0, 0, 1, 0, 1},
    {0, 0, 0, 1, 0, 0, 0, 1},
    {0, 1, 1, 1, 0, 1, 0, 0}
};

// 节点结构体
struct Node {
    int row, col; // 行列坐标
    Node* prev; // 前驱节点
};

// 判断节点是否合法
bool isValidNode(int row, int col) {
    return row >= 0 && row < ROW && col >= 0 && col < COL && maze[row][col] == 0;
}

// 搜索迷宫
Node* searchMaze(int startRow, int startCol, int endRow, int endCol) {
    stack<Node*> s; // 栈
    Node* start = new Node {startRow, startCol, nullptr}; // 起点
    s.push(start); // 入栈

    while (!s.empty()) {
        Node* current = s.top(); // 取出栈顶元素
        s.pop(); // 出栈

        int row = current->row;
        int col = current->col;

        if (row == endRow && col == endCol) { // 到达终点
            return current; // 返回最后一个节点
        }

        // 访问当前节点的四个邻居
        if (isValidNode(row-1, col)) { // 上邻居
            Node* next = new Node {row-1, col, current};
            s.push(next);
        }
        if (isValidNode(row+1, col)) { // 下邻居
            Node* next = new Node {row+1, col, current};
            s.push(next);
        }
        if (isValidNode(row, col-1)) { // 左邻居
            Node* next = new Node {row, col-1, current};
            s.push(next);
        }
        if (isValidNode(row, col+1)) { // 右邻居
            Node* next = new Node {row, col+1, current};
            s.push(next);
        }
    }

    return nullptr; // 没有找到可行路径
}

// 打印路径
void printPath(Node* end) {
    cout << "Path: ";
    while (end != nullptr) {
        cout << "(" << end->row << "," << end->col << ")";
        end = end->prev;
        if (end != nullptr) {
            cout << " -> ";
        }
    }
    cout << endl;
}

int main() {
    Node* end = searchMaze(0, 0, ROW-1, COL-1);
    if (end != nullptr) {
        printPath(end);
    } else {
        cout << "No path found!" << endl;
    }

    return 0;
}