本文共 3200 字，大约阅读时间需要 10 分钟。
为了解决这个问题，我们需要找到从迷宫左上角（1,1）到右下角（5,8）的最短路径。迷宫中使用0表示通路，1表示障碍物。我们可以使用广度优先搜索（BFS）来确保找到最短路径。
方法思路
输入处理：读取迷宫的行数和列数，然后读取迷宫的具体结构。 检查起点：确保起点（1,1）是通路，否则直接输出“NO FOUND”。 BFS初始化：使用队列进行BFS，记录当前路径，避免重复访问同一个点。 路径记录：每次访问一个点时，记录路径，并将未访问的邻居加入队列。 终点检查：如果在BFS过程中找到终点（5,8），输出路径；否则，输出“NO FOUND”。 解决代码
#include #include #include #include using namespace std;// 定义常量const int N = 110;const int INF = 0x3f3f3f3f;int dist[N][2], path[N][2];int m, n;bool visited[N+1][N+1];// 四个方向：上下左右int dx[] = {0, 1, 0, -1};int dy[] = {1, 0, -1, 0};void bfs() { queue > q; vector step; q.push(make_pair(1, 1)); step.clear(); dist[0][0] = 1; path[0][0] = make_pair(1, 1); if (1 == m && 1 == n) { // 起点就是终点 dist[0][0] = 0; path[0][0] = make_pair(1, 1); return; } int found = 0; while (!q.empty()) { auto current = q.front(); q.pop(); int x = current.first, y = current.second; step.push_back(current); if (x == m && y == n) { found = 1; break; } for (int i = 0; i < 4; ++i) { int tx = x + dx[i]; int ty = y + dy[i]; if (tx >= 1 && tx <= n && ty >= 1 && ty <= m) { if (!visited[tx][ty] && g[tx][ty] == 0) { visited[tx][ty] = 1; dist[step.size() - 1][0] = tx; dist[step.size() - 1][1] = ty; path[step.size() - 1][0] = tx; path[step.size() - 1][1] = ty; q.push(make_pair(tx, ty)); } } } } if (found) { for (int i = 0; i < step.size(); ++i) { int x = path[i].first; int y = path[i].second; // 转换为题目要求的1-based索引 cout << x << ","; cout << y << endl; } } else { cout << "NO FOUND" << endl; } } int main() { while (true) { cin >> n >> m; if (m == -1) { break; } // 读取迷宫数据 vector > g(m + 1, vector (n + 1, 0)); for (int i = 1; i <= m; ++i) { string line; while (line.empty()) { getline(cin, line); } vector row; istringstream iss(line); while (row.size() < n) { int num; iss >> num; row.push_back(num); } for (int j = 1; j <= n; ++j) { g[i][j] = row[j - 1]; } } // 检查起点是否是通路 if (g[1][1] != 0) { cout << "NO FOUND" << endl; continue; } // 初始化BFS visited = {{false}}; vector steps; queue > q; q.push(make_pair(1, 1)); visited[1][1] = true; if (1 == m && 1 == n) { cout << "1,1" << endl; continue; } bool success = false; // BFS过程 while (!q.empty()) { auto current = q.front(); q.pop(); int x = current.first, y = current.second; for (int i = 0; i < 4; ++i) { int tx = x + dx[i]; int ty = y + dy[i]; if (tx >= 1 && tx <= n && ty >= 1 && ty <= m) { if (!visited[tx][ty] && g[tx][ty] == 0) { visited[tx][ty] = true; if (tx == m && ty == n) { success = true; break; } // 记录路径 if (steps.empty()) { dist[0][0] = tx; dist[0][1] = ty; path[0][0] = make_pair(tx, ty); steps.push_back(0); } else { dist[steps.size()][0] = tx; dist[steps.size()][1] = ty; path[steps.size()][0] = make_pair(tx, ty); steps.push_back(steps.size()); } q.push(make_pair(tx, ty)); } } } if (success) { break; } } if (success) { for (int i = 0; i < steps.size(); ++i) { int x = path[i].first; int y = path[i].second; // 转换为题目要求的1-based索引 cout << x << ","; cout << y << endl; } } else { cout << "NO FOUND" << endl; } } return 0; }
代码解释
读取输入：程序读取迷宫的行数和列数，接着读取每行的迷宫数据。 BFS初始化：检查起点是否为通路，初始化队列和路径记录数组。 BFS执行：从起点开始，逐层扩展，检查四个方向的邻居是否为通路且未访问过。 路径记录：每次访问一个点时，记录路径，并将邻居加入队列。 终点检查：如果找到终点，输出路径；否则，输出“NO FOUND”。 转载地址：http://pvzqz.baihongyu.com/