P4890 迷宫（基础）

解题思路

第一步，读懂题目。 有一个 n×n 的方格迷宫，数字 0 表示可以走，数字 1 表示障碍物不能走。起点在左上角（1，1），终点是右下角（n，n），只能向上、下、左、右四个方向走，问能不能从起点走到终点。测试数据保证起点和终点都是 0。

第二步，想到用深搜（DFS）。 从起点开始，像走迷宫一样一步一步尝试：能往哪个方向走就往哪个方向走，走不通就退回来换一个方向。把问题交给一个函数 dfs(x, y)，它表示"我正在格子 (x,y)，请帮我看看能不能走到终点"。

第三步，防止绕圈。 走过的格子要标记成 1，就像在地上做个记号，免得在同一块地方转来转去浪费时间。因为 1 本来也表示障碍物，标记成 1 正好表示"这里走过了，不能再走"。

第四步，判断出口。 只要 dfs 走到了 (n,n) 就说明成功，用一个开关 ok 记录下来。四个方向用两个小数组 dx、dy 来表示：上（-1,0）、下（1,0）、左（0,-1）、右（0,1）。还要检查新位置有没有越出迷宫的边界（1 到 n 之间），以及那个格子是不是 0。

边界情况： 如果 n=2，只有四个格子，起点（1,1）到终点（2,2），只要中间的路线能走通就行。起点和终点本身就是 0，所以至少可以从起点出发。全部走完都到不了终点就输出 NO。

参考代码

// 迷宫：判断能否从(1,1)走到(n,n)，0可走1不可走，DFS深搜
#include <iostream>
using namespace std;

int n, g[12][12], ok;   // g存迷宫, ok标记是否到达终点
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

// 从(x,y)出发深搜四个方向
void dfs(int x, int y) {
    if (x == n && y == n) { ok = 1; return; }
    g[x][y] = 1; // 走过标记为障碍,防止回头
    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() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> g[i][j];
    dfs(1, 1);
    cout << (ok ? "YES" : "NO") << endl;
    return 0;
}

复杂度分析

深搜中每个格子最多被访问一次，所以时间复杂度是 O(n²)。n 最大是 10，也就是最多 100 个格子，非常快。空间上只需要存 n×n 的迷宫，也是 O(n²)。