C++ 迷宫求解：最佳通路算法实现

以下是使用 C++ 编写的迷宫求解解决方案，该解决方案使用两种算法：使用栈寻找最短路径和使用队列确定最短路径。

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

struct Node {
    int x, y, dir;
    Node(int _x, int _y, int _dir) : x(_x), y(_y), dir(_dir) {}
};

// 定义方向常量
const int RIGHT = 1;
const int DOWN = 2;
const int LEFT = 3;
const int UP = 4;

// 定义迷宫和访问矩阵
int maze[101][101];
bool visited[101][101];

// 定义移动方向数组
int dx[5] = {0, 1, 0, -1, 0};
int dy[5] = {0, 0, 1, 0, -1};

// 定义迷宫的行数和列数
int M, N;

// 判断坐标是否有效
bool isValid(int x, int y) {
    return x >= 1 && x <= M && y >= 1 && y <= N && maze[x][y] == 1 && !visited[x][y];
}

// 使用栈寻找最短路径
bool findShortestPath(int start_x, int start_y, int end_x, int end_y) {
    stack<Node> s;
    s.push(Node(start_x, start_y, 0));
    visited[start_x][start_y] = true;

    while (!s.empty()) {
        Node currentNode = s.top();
        s.pop();

        int x = currentNode.x;
        int y = currentNode.y;
        int dir = currentNode.dir;

        if (x == end_x && y == end_y) {
            return true;
        }

        for (int i = dir + 1; i <= 4; i++) {
            int new_x = x + dx[i];
            int new_y = y + dy[i];

            if (isValid(new_x, new_y)) {
                visited[new_x][new_y] = true;
                s.push(Node(new_x, new_y, 0));
                break;
            }
        }
    }

    return false;
}

// 使用队列确定最短路径
bool findShortestPathBFS(int start_x, int start_y, int end_x, int end_y) {
    queue<Node> q;
    q.push(Node(start_x, start_y, 0));
    visited[start_x][start_y] = true;

    while (!q.empty()) {
        Node currentNode = q.front();
        q.pop();

        int x = currentNode.x;
        int y = currentNode.y;
        int dir = currentNode.dir;

        if (x == end_x && y == end_y) {
            return true;
        }

        for (int i = 1; i <= 4; i++) {
            int new_x = x + dx[i];
            int new_y = y + dy[i];

            if (isValid(new_x, new_y)) {
                visited[new_x][new_y] = true;
                q.push(Node(new_x, new_y, 0));
            }
        }
    }

    return false;
}

// 输出路径
void printPath(int start_x, int start_y, int end_x, int end_y) {
    stack<Node> s;
    s.push(Node(end_x, end_y, 0));

    while (!s.empty()) {
        Node currentNode = s.top();
        s.pop();

        int x = currentNode.x;
        int y = currentNode.y;
        int dir = currentNode.dir;

        cout << '(' << x << ',' << y << ',' << dir << ')';
        if (s.size() % 5 == 0) {
            cout << endl;
        } else if (!s.empty()) {
            cout << ',';
        }

        for (int i = dir; i <= 4; i++) {
            int new_x = x + dx[i];
            int new_y = y + dy[i];

            if (isValid(new_x, new_y)) {
                s.push(Node(new_x, new_y, i));
                break;
            }
        }
    }
}

int main() {
    while (cin >> M >> N && M != 0 && N != 0) {
        // 初始化迷宫和访问矩阵
        for (int i = 1; i <= M; i++) {
            for (int j = 1; j <= N; j++) {
                cin >> maze[i][j];
                visited[i][j] = false;
            }
        }

        int start_x = 1, start_y = 1;
        int end_x = M, end_y = N;

        // 使用栈找最短路径
        if (findShortestPath(start_x, start_y, end_x, end_y)) {
            printPath(start_x, start_y, end_x, end_y);
            cout << endl;
        } else {
            // 使用队列找最短路径
            if (findShortestPathBFS(start_x, start_y, end_x, end_y)) {
                printPath(start_x, start_y, end_x, end_y);
                cout << endl;
            } else {
                cout << '没有通路' << endl;
            }
        }
    }

    return 0;
}

请用编译器运行该代码，并将迷宫数据输入到控制台，程序将输出最佳通路或没有通路的结果。