P4897 森林探险（入门）

解题思路

第一步，读懂题目。 小童在 n×n 的迷宫里走，'.' 是可以走的路，'#' 是障碍物不能走。他只能上下左右走，问能不能从起点 A 走到终点 B。地图左上角是 (1,1)。如果起点或终点本身是 '#'，直接算走不到。题目给 t 组数据，每组都要回答一次。

第二步，用深搜探路。 从起点 (sx,sy) 出发，往四个方向试探：能走的路（'.'）就走进去，继续往前探；走不通就退回来换方向。只要某条路走到了终点 (ex,ey)，就说明能办到。

第三步，防止死循环。 走过的路要立刻改成 '#'，表示"这条路已经试过了"，不然会在迷宫里面转圈出不来。因为 '#' 本来就不能走，改成 '#' 正好拦住回头路。

第四步，处理特殊要求。 题目特别强调：如果起点或者终点有一个是 '#'，就看成无法办到。所以深搜之前要先检查这两个点。另外每组数据都要重新读入地图并重置答案，所以 ok 标记要在每组开头清零。

具体例子： 第一组 3×3 迷宫，从 (1,1) 到 (3,3) 有条路能走通，输出 YES；第二组 5×5 迷宫被 # 挡住了，走不到，输出 NO。

边界情况： t 和 n 最大都是 50，一组迷宫最多 2500 个格子，深搜完全来得及。注意读地图时是一行一个字符串，用字符方式逐个读入即可。

参考代码

// 森林探险：t组迷宫,判断起点能否走到终点,.可走#不可走
#include <iostream>
using namespace std;

int n, sx, sy, ex, ey, ok;
char g[55][55]; // 迷宫地图
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

// 从(x,y)向上下左右深搜
void dfs(int x, int y) {
    if (x == ex && y == ey) { ok = 1; return; }
    g[x][y] = '#'; // 走过标记为不可走
    for (int k = 0; k < 4; k++) {
        int nx = x + dx[k], ny = y + dy[k];
        if (nx >= 1 && nx <= n && ny >= 1 && ny <= n && g[nx][ny] == '.' && !ok)
            dfs(nx, ny);
    }
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                cin >> g[i][j];
        cin >> sx >> sy >> ex >> ey;
        ok = 0;
        if (g[sx][sy] == '#' || g[ex][ey] == '#')
            cout << "NO" << endl; // 起点或终点不可走
        else {
            dfs(sx, sy);
            cout << (ok ? "YES" : "NO") << endl;
        }
    }
    return 0;
}

复杂度分析

每组数据每个格子最多被访问一次，时间复杂度是 O(t×n²)。t、n 最大都是 50，也就是最多 50×2500=125000 个格子，很快。空间上需要存一张 n×n 的地图，是 O(n²)。