迷宫问题 问题描述:给定一个迷宫，求出所有从入口到出口的路径，具体要求如下: 迷宫以16*16的矩阵存储在本地文本文件中，格式自定义。 迷宫中的障碍物要占到一定比例。 必须使用非递归的形式求解。 必须绘制出迷宫和求解的路径(命令行或GUI均可，可以只输出其中一条)。 当无解时能提示相应信息。

好的，这是一个比较复杂的问题，需要用到图论和搜索算法。我会尽力给你解答，但是可能会比较长，请耐心阅读。

首先，我们需要从文本文件中读取迷宫，生成一个图。假设入口为S，出口为T，我们可以使用邻接表来表示这个图。每个节点表示一个迷宫的位置，每个节点的邻居表示可以向上下左右四个方向行走的位置。如果一个位置为障碍物，则这个节点没有邻居。我们可以用一个二维数组来表示邻接表，数组的每个元素是一个链表，表示这个节点的所有邻居。

读取迷宫并生成邻接表的代码如下：

#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

const int N = 16;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};

struct Node {
    int x, y;
    vector<int> neighbors;
};

vector<Node> graph(N * N);
char maze[N][N];

bool in_maze(int x, int y) {
    return x >= 0 && x < N && y >= 0 && y < N;
}

void add_edge(int u, int v) {
    graph[u].neighbors.push_back(v);
    graph[v].neighbors.push_back(u);
}

void build_graph() {
    ifstream fin("maze.txt");
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            fin >> maze[i][j];
            if (maze[i][j] != '#') {
                int u = i * N + j;
                Node &node = graph[u];
                node.x = i;
                node.y = j;
                for (int k = 0; k < 4; k++) {
                    int x = i + dx[k], y = j + dy[k];
                    if (in_maze(x, y) && maze[x][y] != '#') {
                        int v = x * N + y;
                        add_edge(u, v);
                    }
                }
            }
        }
    }
    fin.close();
}

下一步，我们需要使用广度优先搜索来找到从S到T的所有路径。这里我们可以使用一个队列来存储搜索中的状态。初始状态为S，每次从队列中取出一个状态，并将它的邻居加入队列中。如果邻居是T，则表示我们找到了一条路径。我们可以用一个数组来存储每个节点的前驱节点，这样可以在找到一条路径后，从T开始沿着前驱节点一直走到S，就可以得到一条从S到T的路径。

搜索的代码如下：

#include <queue>

vector<int> pre(N * N, -1);

bool bfs(int s, int t) {
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : graph[u].neighbors) {
            if (pre[v] == -1) {
                pre[v] = u;
                if (v == t) {
                    return true;
                }
                q.push(v);
            }
        }
    }
    return false;
}

最后，我们可以将路径输出到命令行或者GUI中，也可以将路径绘制在迷宫图中。这里我以命令行输出为例，代码如下：

void print_path(int s, int t) {
    if (pre[t] == -1) {
        cout << "No path from S to T" << endl;
        return;
    }
    vector<int> path;
    for (int u = t; u != s; u = pre[u]) {
        path.push_back(u);
    }
    path.push_back(s);
    reverse(path.begin(), path.end());
    for (int u : path) {
        int x = graph[u].x, y = graph[u].y;
        maze[x][y] = '*';
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cout << maze[i][j] << ' ';
        }
        cout << endl;
    }
}

完整的代码如下：

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

const int N = 16;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};

struct Node {
    int x, y;
    vector<int> neighbors;
};

vector<Node> graph(N * N);
char maze[N][N];

bool in_maze(int x, int y) {
    return x >= 0 && x < N && y >= 0 && y < N;
}

void add_edge(int u, int v) {
    graph[u].neighbors.push_back(v);
    graph[v].neighbors.push_back(u);
}

void build_graph() {
    ifstream fin("maze.txt");
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            fin >> maze[i][j];
            if (maze[i][j] != '#') {
                int u = i * N + j;
                Node &node = graph[u];
                node.x = i;
                node.y = j;
                for (int k = 0; k < 4; k++) {
                    int x = i + dx[k], y = j + dy[k];
                    if (in_maze(x, y) && maze[x][y] != '#') {
                        int v = x * N + y;
                        add_edge(u, v);
                    }
                }
            }
        }
    }
    fin.close();
}

vector<int> pre(N * N, -1);

bool bfs(int s, int t) {
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : graph[u].neighbors) {
            if (pre[v] == -1) {
                pre[v] = u;
                if (v == t) {
                    return true;
                }
                q.push(v);
            }
        }
    }
    return false;
}

void print_path(int s, int t) {
    if (pre[t] == -1) {
        cout << "No path from S to T" << endl;
        return;
    }
    vector<int> path;
    for (int u = t; u != s; u = pre[u]) {
        path.push_back(u);
    }
    path.push_back(s);
    reverse(path.begin(), path.end());
    for (int u : path) {
        int x = graph[u].x, y = graph[u].y;
        maze[x][y] = '*';
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cout << maze[i][j] << ' ';
        }
        cout << endl;
    }
}

int main() {
    build_graph();
    int s = 0, t = N * N - 1;
    if (bfs(s, t)) {
        print_path(s, t);
    } else {
        cout << "No path from S to T" << endl;
    }
    return 0;
}