当前位置：首页 > news >正文

C++题目迷宫（1~8）详解

news 2026/7/24 22:09:10

1. 迷宫问题概述

迷宫问题是算法竞赛和编程学习中经典的搜索类题目，通常要求在一个二维网格中，从起点出发，寻找一条通往终点的路径。这类题目是练习深度优先搜索（DFS）和广度优先搜索（BFS）算法的绝佳场景。本文将详细解析从基础到进阶的8个迷宫类题目，涵盖DFS、BFS、记忆化搜索、双向BFS等多种解法。

2. 基础迷宫（题目1-3）

2.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; vector<string> 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 vector<vector<bool>> visited(N, vector<bool>(M, false)); queue<Point> 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核心循环修改 queue<Node> 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 // 记录前驱 vector<vector<pair<int, int>>> pre(N, vector<pair<int, int>>(M, {-1, -1})); vector<vector<char>> dir(N, vector<char>(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-6）

3.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 vector<vector<int>> dist(N, vector<int>(M, INT_MAX)); priority_queue<Node, vector<Node>, greater<Node>> 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初始化 queue<State> 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-8）

4.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; }