# 迷宫游戏 ## 题目背景 假设你是一位游戏开发者，正在为一款冒险类游戏设计一个关卡。在这个关卡中，玩家需要通过某些方式探索一个迷宫并找到宝藏。 ## 题目描述 给定一个包含障碍物和空地的迷宫地图，请编写程序，判断是否存在一条从起点到终点的路径，并输出路径上经过的点数。 ## 输入格式 第1行包含两个正整数 n 和 m，分别表示迷宫的行数和列数（1 ≤ n, m ≤ 100）。 接下来 n 行，每行包含 m 个字符，其中 "." 表示空地，"#" 表示障碍物，"S" 表示起点，"E" 表示终点。 ## 输出格式 如果存在从起点到终点的路径，则输出路径上经过的点数（不包括起点和终点），否则输出 "No path". ## 样例 #1 ### 样例输入 #1 ``` 5 6 S.#... #.###. ....#. ###.#. ...E.. ``` ### 样例输出 #1 ``` 8 ``` ## 提示 对于100%的数据，保证迷宫的行数和列数：1 ≤ n, m ≤ 100 用C++完成这道题

这道题可以使用深度优先搜索（DFS）或广度优先搜索（BFS）算法来解决。下面是使用DFS的方法：

首先，我们可以定义一个二维数组来表示迷宫，用来记录每个位置的状态。0表示空地，1表示障碍物，2表示已经访问过的位置。

我们可以定义一个递归函数来进行深度优先搜索。递归函数的参数包括当前位置的坐标、当前路径长度和迷宫地图。

在递归函数中，我们首先判断当前位置是否越界或者是障碍物，如果是，则返回。

然后我们判断当前位置是否是终点，如果是，则输出当前路径长度，并返回。

否则，我们将当前位置标记为已访问，并对当前位置的上、下、左、右四个方向进行递归搜索。

最后，在主函数中，我们找到起点的位置，并调用递归函数进行搜索。

下面是一个C++的实现示例：

#include <iostream>
#include <vector>

using namespace std;

int n, m;
vector<vector<int>> maze;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

void dfs(int x, int y, int len) {
    if (x < 0 || x >= n || y < 0 || y >= m || maze[x][y] == 1 || maze[x][y] == 2) {
        return;
    }

    if (maze[x][y] == 3) {
        cout << len << endl;
        return;
    }

    maze[x][y] = 2;

    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        dfs(nx, ny, len + 1);
    }

    maze[x][y] = 0;
}

int main() {
    cin >> n >> m;

    maze.resize(n, vector<int>(m));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            char c;
            cin >> c;
            if (c == '#') {
                maze[i][j] = 1;
            } else if (c == 'S') {
                maze[i][j] = 0;
            } else if (c == 'E') {
                maze[i][j] = 3;
            }
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (maze[i][j] == 0) {
                dfs(i, j, 0);
            }
        }
    }

    cout << "No path" << endl;

    return 0;
}

希望这可以帮助到你！如果有任何问题，请随时问我。