C++题目迷宫（1~8）详解 1. 迷宫问题概述迷宫问题是算法竞赛和编程学习中经典的搜索类题目通常要求在一个二维网格中从起点出发寻找一条通往终点的路径。这类题目是练习深度优先搜索DFS和广度优先搜索BFS算法的绝佳场景。本文将详细解析从基础到进阶的8个迷宫类题目涵盖DFS、BFS、记忆化搜索、双向BFS等多种解法。2. 基础迷宫题目1-32.1 题目1能否走出迷宫问题描述给定一个N×M的迷宫S表示起点T表示终点*表示墙壁.表示通路。判断从起点能否到达终点。输入格式第一行两个整数N, M。接下来N行每行M个字符表示迷宫。输出格式如果能走到终点输出YES否则输出NO。#include iostream #include vector #include queue using namespace std; struct Point { int x, y; }; int main() { int N, M; cin N M; vectorstring maze(N); Point start, end; for (int i 0; i N; i) { cin maze[i]; for (int j 0; j M; j) { if (maze[i][j] S) start {i, j}; if (maze[i][j] T) end {i, j}; } } // BFS vectorvectorbool visited(N, vectorbool(M, false)); queuePoint q; q.push(start); visited[start.x][start.y] true; int dx[4] {0, 0, 1, -1}; int dy[4] {1, -1, 0, 0}; while (!q.empty()) { Point cur q.front(); q.pop(); if (cur.x end.x cur.y end.y) { cout YES endl; return 0; } for (int i 0; i 4; i) { int nx cur.x dx[i]; int ny cur.y dy[i]; if (nx 0 nx N ny 0 ny M maze[nx][ny] ! * !visited[nx][ny]) { visited[nx][ny] true; q.push({nx, ny}); } } } cout NO endl; return 0; }核心思路标准的BFS模板。使用队列逐层探索用visited数组避免重复访问。时间复杂度O(N×M)。2.2 题目2输出最短路径长度问题描述在题目1的基础上如果能走到终点输出最短路径的步数。解法在BFS过程中记录每个点到起点的距离。当到达终点时该距离即为最短路径长度。// 在BFS队列中存储步数信息 struct Node { int x, y, step; }; // BFS核心循环修改 queueNode q; q.push({start.x, start.y, 0}); visited[start.x][start.y] true; while (!q.empty()) { Node cur q.front(); q.pop(); if (cur.x end.x cur.y end.y) { cout cur.step endl; return 0; } for (int i 0; i 4; i) { int nx cur.x dx[i]; int ny cur.y dy[i]; if (nx 0 nx N ny 0 ny M maze[nx][ny] ! * !visited[nx][ny]) { visited[nx][ny] true; q.push({nx, ny, cur.step 1}); } } }2.3 题目3输出最短路径本身问题描述不仅要输出最短路径长度还要输出具体的路径如DRRURRDD其中D表示向下R表示向右等。解法在BFS过程中记录每个点的前驱节点和移动方向。到达终点后从终点回溯到起点逆序得到路径。// 方向字符映射 char dirChar[4] {R, L, D, U}; // 对应dx, dy // 记录前驱 vectorvectorpairint, int pre(N, vectorpairint, int(M, {-1, -1})); vectorvectorchar dir(N, vectorchar(M, )); // BFS中更新前驱信息 if (条件满足) { visited[nx][ny] true; pre[nx][ny] {cur.x, cur.y}; dir[nx][ny] dirChar[i]; q.push({nx, ny, cur.step 1}); } // 回溯输出路径 if (找到终点) { string path ; int x end.x, y end.y; while (!(x start.x y start.y)) { path dir[x][y]; int px pre[x][y].first; int py pre[x][y].second; x px; y py; } reverse(path.begin(), path.end()); cout path endl; }3. 进阶迷宫题目4-63.1 题目4带权迷宫最短路径问题描述迷宫中的每个格子有一个通过代价正整数求从起点到终点的最小代价路径。输入N, M然后是N×M的代价矩阵。解法将BFS改为Dijkstra算法或0-1 BFS如果代价只有0和1。使用优先队列小顶堆确保每次扩展当前代价最小的点。#include queue #include climits using namespace std; struct Node { int x, y, cost; bool operator(const Node other) const { return cost other.cost; } }; // Dijkstra vectorvectorint dist(N, vectorint(M, INT_MAX)); priority_queueNode, vectorNode, greaterNode pq; dist[start.x][start.y] 0; pq.push({start.x, start.y, 0}); while (!pq.empty()) { Node cur pq.top(); pq.pop(); if (cur.cost dist[cur.x][cur.y]) continue; // 旧值跳过 if (cur.x end.x cur.y end.y) { cout cur.cost endl; break; } for (int i 0; i 4; i) { int nx cur.x dx[i]; int ny cur.y dy[i]; if (nx 0 nx N ny 0 ny M maze[nx][ny] ! *) { int newCost cur.cost costMatrix[nx][ny]; // 加上格子代价 if (newCost dist[nx][ny]) { dist[nx][ny] newCost; pq.push({nx, ny, newCost}); } } } }3.2 题目5多出口迷宫问题描述迷宫中有多个出口T求从起点到任意一个出口的最短路径。解法BFS不变终止条件改为maze[nx][ny] T。因为BFS首次遇到出口时即为最短路径。3.3 题目6有门和钥匙的迷宫问题描述迷宫中有门用大写字母表示如A和对应的钥匙用小写字母表示如a。只有拿到钥匙才能通过对应的门。解法状态压缩BFS。将钥匙的持有状态作为第三维状态。visited[x][y][keyState]表示在位置(x,y)持有钥匙状态keyState是否访问过。struct State { int x, y, keys, step; }; // BFS初始化 queueState q; q.push({start.x, start.y, 0, 0}); visited[start.x][start.y][0] true; while (!q.empty()) { State cur q.front(); q.pop(); if (cur.x end.x cur.y end.y) { return cur.step; } for (int i 0; i 4; i) { int nx cur.x dx[i]; int ny cur.y dy[i]; if (nx 0 || nx N || ny 0 || ny M) continue; char c maze[nx][ny]; int newKeys cur.keys; // 如果是钥匙更新状态 if (c a c z) { newKeys | (1 (c - a)); } // 如果是门检查是否有对应钥匙 if (c A c Z) { if (!(newKeys (1 (c - A)))) { continue; // 没有钥匙不能通过 } } if (c * || visited[nx][ny][newKeys]) continue; visited[nx][ny][newKeys] true; q.push({nx, ny, newKeys, cur.step 1}); } }4. 高级迷宫题目7-84.1 题目7传送门迷宫问题描述迷宫中存在若干对传送门进入一个传送门会立即传送到对应的另一个传送门。解法BFS中当走到传送门位置时除了向四个方向扩展还要将传送到的目标位置也加入队列步数不变。需要预处理传送门的对应关系。4.2 题目8限时迷宫K步内到达问题描述在K步内从起点到达终点求是否存在这样的路径。解法DFS 剪枝 或 BFS限制深度。使用DFS时需要记录当前步数超过K则剪枝。使用BFS时当步数超过K仍未找到终点即可判定无解。// DFS解法框架 bool dfs(int x, int y, int step) { if (step K) return false; if (x end.x y end.y) return true; visited[x][y] true; for (int i 0; i 4; i) { int nx x dx[i]; int ny y dy[i]; if (nx 0 nx N ny 0 ny M maze[nx][ny] ! * !visited[nx][ny]) { if (dfs(nx, ny, step 1)) return true; } } visited[x][y] false; // 回溯 return false; }5. 总结与技巧BFS求最短路径、最少步数。使用队列空间复杂度较高。DFS求是否存在路径、所有路径。使用递归或栈注意剪枝和回溯。记忆化搜索结合DFS与动态规划避免重复计算。状态压缩当问题有多个状态如钥匙、传送门时将状态作为搜索维度。双向BFS从起点和终点同时开始BFS当两边的搜索相遇时结束。适用于状态空间较大的情况。掌握这8类迷宫问题就能应对大多数搜索类竞赛题目。关键在于根据题目特点选择合适的搜索策略并熟练实现。