迷宫探秘：求解扶苏走出数字矩阵迷宫所需步数及循环判定

```cpp #include <iostream> #include <vector> using namespace std; // 迷宫类，用于处理迷宫问题 class Maze { private: int n, m; vector<vector<int>> grid; // 检查是否走出迷宫 bool isOutOfMaze(int i, int j) { return i < 1 || i > n || j < 1 || j > m; } // 模拟移动过程 int move(int i, int j) { vector<vector<bool>> visited(n + 1, vector<bool>(m + 1, false)); int steps = 0; while (!isOutOfMaze(i, j)) { if (visited[i][j]) { return -1; // 陷入循环，无法走出 } visited[i][j] = true; steps++; switch (grid[i - 1][j - 1]) { case 1: i--; break; case 2: i++; break; case 3: j--; break; case 4: j++; break; } } return steps; } public: Maze(int n, int m) : n(n), m(m) { grid.resize(n, vector<int>(m)); } // 输入迷宫矩阵 void inputGrid() { for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> grid[i][j]; } } } // 处理查询 int query(int x, int y) { return move(x, y); } }; int main() { int n, m, q; cin >> n >> m >> q; Maze maze(n, m); maze.inputGrid(); for (int i = 0; i < q; i++) { int x, y; cin >> x >> y; cout << maze.query(x, y) << endl; } return 0; } ``` 代码解释： 1. `Maze`类： - 该类封装了迷宫的相关操作，包括存储迷宫矩阵、检查是否走出迷宫、模拟移动过程和处理查询。 - `isOutOfMaze`方法：用于检查当前位置是否走出迷宫。 - `move`方法：模拟扶苏在迷宫中的移动过程，使用`visited`数组记录已经访问过的位置，若再次访问到已访问的位置，则说明陷入循环，无法走出迷宫，返回 -1；否则，根据当前位置的数字进行移动，并增加步数，直到走出迷宫。 - `inputGrid`方法：用于输入迷宫矩阵。 - `query`方法：调用`move`方法处理查询。 2. `main`函数： - 读取输入的迷宫行数`n`、列数`m`和查询数`q`。 - 创建`Maze`对象并输入迷宫矩阵。 - 循环处理`q`次查询，读取每次查询的初始位置，调用`query`方法并输出结果。 复杂度分析： - 时间复杂度：每次查询的时间复杂度为$O(nm)$，因为在最坏情况下，可能需要遍历迷宫中的所有位置。 - 空间复杂度：主要用于存储迷宫矩阵和`visited`数组，空间复杂度为$O(nm)$。 ######[AI问答 | 819点数解答 | 2025-11-26 19:27:35]