给定一个M*N的迷宫，分别利用栈和队列求从一条指定入口到出口的路径。所求路径必须是简单路径，即在所求路径上不能重复出现同一通道块。 c++代码

以下是使用栈求解迷宫路径的C++代码：

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

const int MAX_SIZE = 100; // 迷宫的最大尺寸

// 迷宫结构体
struct Maze {
    int row, col; // 迷宫的行数和列数
    int entrance[2], exit[2]; // 入口和出口的坐标
    char data[MAX_SIZE][MAX_SIZE]; // 迷宫数据
};

// 定义一个坐标结构体
struct Point {
    int x, y;
};

// 栈结构体
struct Stack {
    Point data[MAX_SIZE * MAX_SIZE];
    int top;
};

// 初始化栈
void initStack(Stack &s) {
    s.top = -1;
}

// 判断栈是否为空
bool isEmpty(Stack s) {
    return s.top == -1;
}

// 入栈
void push(Stack &s, Point p) {
    s.data[++s.top] = p;
}

// 出栈
void pop(Stack &s) {
    if (!isEmpty(s)) {
        s.top--;
    }
}

// 获取栈顶元素
Point top(Stack s) {
    return s.data[s.top];
}

// 标记已经走过的点
void mark(int mark[MAX_SIZE][MAX_SIZE], Point p) {
    mark[p.x][p.y] = 1;
}

// 判断点是否越界
bool outOfBounds(Maze m, Point p) {
    return p.x < 0 || p.x >= m.row || p.y < 0 || p.y >= m.col;
}

// 判断当前点是否可以通过
bool pass(Maze m, int mark[MAX_SIZE][MAX_SIZE], Point p) {
    return !outOfBounds(m, p) && m.data[p.x][p.y] == '0' && mark[p.x][p.y] == 0;
}

// 利用栈求解迷宫路径
void findPathByStack(Maze m, Point start, Point end) {
    Stack s;
    int mark[MAX_SIZE][MAX_SIZE] = {0}; // 标记迷宫中已经走过的点
    initStack(s);
    push(s, start);
    mark(mark, start);
    while (!isEmpty(s)) {
        Point cur = top(s);
        if (cur.x == end.x && cur.y == end.y) { // 当前点为终点
            cout << "迷宫路径为：" << endl;
            Stack path; // 利用栈保存路径
            initStack(path);
            while (!isEmpty(s)) { // 回溯路径
                path.data[++path.top] = top(s);
                pop(s);
            }
            while (!isEmpty(path)) { // 输出路径
                Point p = path.data[path.top];
                path.top--;
                cout << "(" << p.x << ", " << p.y << ")" << endl;
            }
            return;
        }
        bool found = false; // 是否找到下一个点
        // 按照右、下、左、上的顺序查找下一个点
        Point next[4] = {{cur.x, cur.y + 1}, {cur.x + 1, cur.y}, {cur.x, cur.y - 1}, {cur.x - 1, cur.y}};
        for (int i = 0; i < 4; i++) {
            if (pass(m, mark, next[i])) { // 如果该点可以通过
                push(s, next[i]);
                mark(mark, next[i]);
                found = true;
                break;
            }
        }
        if (!found) { // 如果没有找到下一个点，则回溯
            pop(s);
        }
    }
    cout << "没有找到迷宫路径" << endl;
}

int main() {
    Maze m;
    cout << "请输入迷宫的行数和列数：" << endl;
    cin >> m.row >> m.col;
    cout << "请输入迷宫的数据：" << endl;
    for (int i = 0; i < m.row; i++) {
        for (int j = 0; j < m.col; j++) {
            cin >> m.data[i][j];
        }
    }
    cout << "请输入入口和出口的坐标：" << endl;
    cin >> m.entrance[0] >> m.entrance[1] >> m.exit[0] >> m.exit[1];
    Point start = {m.entrance[0], m.entrance[1]};
    Point end = {m.exit[0], m.exit[1]};
    findPathByStack(m, start, end);
    return 0;
}

以下是使用队列求解迷宫路径的C++代码：

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

const int MAX_SIZE = 100; // 迷宫的最大尺寸

// 迷宫结构体
struct Maze {
    int row, col; // 迷宫的行数和列数
    int entrance[2], exit[2]; // 入口和出口的坐标
    char data[MAX_SIZE][MAX_SIZE]; // 迷宫数据
};

// 定义一个坐标结构体
struct Point {
    int x, y;
};

// 队列结构体
struct Queue {
    Point data[MAX_SIZE * MAX_SIZE];
    int front, rear;
};

// 初始化队列
void initQueue(Queue &q) {
    q.front = q.rear = -1;
}

// 判断队列是否为空
bool isEmpty(Queue q) {
    return q.front == -1;
}

// 入队
void enqueue(Queue &q, Point p) {
    q.data[++q.rear] = p;
    if (q.front == -1) {
        q.front = 0;
    }
}

// 出队
void dequeue(Queue &q) {
    if (!isEmpty(q)) {
        q.front++;
        if (q.front > q.rear) {
            q.front = q.rear = -1;
        }
    }
}

// 获取队头元素
Point front(Queue q) {
    return q.data[q.front];
}

// 标记已经走过的点
void mark(int mark[MAX_SIZE][MAX_SIZE], Point p) {
    mark[p.x][p.y] = 1;
}

// 判断点是否越界
bool outOfBounds(Maze m, Point p) {
    return p.x < 0 || p.x >= m.row || p.y < 0 || p.y >= m.col;
}

// 判断当前点是否可以通过
bool pass(Maze m, int mark[MAX_SIZE][MAX_SIZE], Point p) {
    return !outOfBounds(m, p) && m.data[p.x][p.y] == '0' && mark[p.x][p.y] == 0;
}

// 利用队列求解迷宫路径
void findPathByQueue(Maze m, Point start, Point end) {
    Queue q;
    int mark[MAX_SIZE][MAX_SIZE] = {0}; // 标记迷宫中已经走过的点
    initQueue(q);
    enqueue(q, start);
    mark(mark, start);
    while (!isEmpty(q)) {
        Point cur = front(q);
        if (cur.x == end.x && cur.y == end.y) { // 当前点为终点
            cout << "迷宫路径为：" << endl;
            Queue path; // 利用队列保存路径
            initQueue(path);
            while (!isEmpty(q)) { // 回溯路径
                path.data[++path.rear] = front(q);
                dequeue(q);
            }
            while (!isEmpty(path)) { // 输出路径
                Point p = path.data[path.front];
                path.front++;
                cout << "(" << p.x << ", " << p.y << ")" << endl;
            }
            return;
        }
        // 按照右、下、左、上的顺序查找下一个点
        Point next[4] = {{cur.x, cur.y + 1}, {cur.x + 1, cur.y}, {cur.x, cur.y - 1}, {cur.x - 1, cur.y}};
        for (int i = 0; i < 4; i++) {
            if (pass(m, mark, next[i])) { // 如果该点可以通过
                enqueue(q, next[i]);
                mark(mark, next[i]);
            }
        }
        dequeue(q);
    }
    cout << "没有找到迷宫路径" << endl;
}

int main() {
    Maze m;
    cout << "请输入迷宫的行数和列数：" << endl;
    cin >> m.row >> m.col;
    cout << "请输入迷宫的数据：" << endl;
    for (int i = 0; i < m.row; i++) {
        for (int j = 0; j < m.col; j++) {
            cin >> m.data[i][j];
        }
    }
    cout << "请输入入口和出口的坐标：" << endl;
    cin >> m.entrance[0] >> m.entrance[1] >> m.exit[0] >> m.exit[1];
    Point start = {m.entrance[0], m.entrance[1]};
    Point end = {m.exit[0], m.exit[1]};
    findPathByQueue(m, start, end);
    return 0;
}