24 · DFS 与回溯：网格搜索与剪枝

上一节在“1..n 的数字”上做决策，候选集是下标。这一节把决策搬到网格上：每层的候选集变成上下左右四格。网格搜索会逼出一个上一节没遇到过的问题——同一个格子允不允许被两条路径共用。这一个问题的答案决定了标记要不要撤销，而它是一行代码的差别、两种完全不同的算法。

#include <bits/stdc++.h>
using namespace std;

int n = 3, m = 4;                          // 3 行 4 列
int dx[4] = {-1, 1, 0, 0};                 // 上 下 左 右
int dy[4] = {0, 0, -1, 1};

int main() {
    int x = 1, 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 > m) continue;   // 越界的两个方向被跳过
        printf("(%d,%d) ", nx, ny);        // 输出 (2,1) (1,2)
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int n = 4;

int main() {
    for (int i = 1; i <= n; ++i) {          // 主对角线编号 i - j + n
        for (int j = 1; j <= n; ++j) printf("%2d", i - j + n);
        printf("\n");
    }
    printf("\n");
    for (int i = 1; i <= n; ++i) {          // 副对角线编号 i + j
        for (int j = 1; j <= n; ++j) printf("%2d", i + j);
        printf("\n");
    }
    return 0;
}
/* 第一张：4 3 2 1 / 5 4 3 2 / 6 5 4 3 / 7 6 5 4
   第二张：2 3 4 5 / 3 4 5 6 / 4 5 6 7 / 5 6 7 8
   每一条斜线上的数字都相同 —— 这就是“一条斜线一个下标” */

网格上的 DFS 只有两种命运，先分清它们，再动手写。下面这张表是全节最该记住的东西。

差别只有一行，但判断依据很清楚：问“块”就把标记留在原地，问“路”就必须把标记还回去。因为块一旦确定就不再改变，路则是一条一条试出来的。

#include <bits/stdc++.h>
using namespace std;

int n, m, ans;
int g[105][105];                          // 0 空格，1 未访问的格子，2 已归入某块
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

void dfs(int x, int y) {
    g[x][y] = 2;                          // 标记“已访问”：直接改原图，省一个 vis 数组
    for (int k = 0; k < 4; ++k) {
        int nx = x + dx[k], ny = y + dy[k];
        if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
        if (g[nx][ny] != 1) continue;     // 不是未访问的格子就不走
        dfs(nx, ny);
    }
    /* 这里没有 g[x][y] = 1 —— 连通块不撤销 */
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) cin >> g[i][j];

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if (g[i][j] == 1) { ++ans; dfs(i, j); }   // 每从一个没访问过的格子出发，就多一块
    cout << ans << "\n";
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int n, m, t, sx, sy, fx, fy, ans;
int g[10][10];              // 1 = 障碍或本路径已走过（两者都等于“不能走”）
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

void dfs(int x, int y) {
    if (x == fx && y == fy) {           // 到终点：这条路径成立，计数后立刻返回
        ++ans;
        return;                         // 不返回就会从这里继续走，把一条路径数成多条
    }
    for (int k = 0; k < 4; ++k) {
        int nx = x + dx[k], ny = y + dy[k];
        if (nx < 1 || nx > n || ny < 1 || ny > m) continue;   // 先判越界
        if (g[nx][ny]) continue;                             // 障碍 / 本路径已走过
        g[nx][ny] = 1;                  // ① 占位：这一格在本路径上用掉了
        dfs(nx, ny);                    // ② 递进
        g[nx][ny] = 0;                  // ③ 还原：别的路径还要用这一格
    }
}

int main() {
    cin >> n >> m >> t >> sx >> sy >> fx >> fy;
    for (int i = 1; i <= t; ++i) {
        int x, y; cin >> x >> y;
        g[x][y] = 1;                    // 障碍也记成 1，省掉单独的判断
    }
    g[sx][sy] = 1;                      // 起点算“已走过”，否则路径可以绕回起点
    dfs(sx, sy);
    cout << ans << "\n";
    return 0;
}

搜索慢，唯一的原因是分支太多。剪枝就是在“往下走之前”判一句，把整棵子树砍掉——价码是 O(1)，收益可能是指数级。三类剪枝必须能一眼分清。

三类的共同点：判断都在进入下一层之前，代价 O(1)，省下的是一整棵子树。所以剪枝永远比在叶子上优化常数划算——叶子数量本来就是指数的。

八皇后是“可行性剪枝做到极致”的例子：每行放一个棋子，行冲突自动消失；剩下的列与两条斜线，各用一个 bool 数组记着有没有被占，判一次冲突只要三次内存访问。8 皇后裸枚举是 8⁸ = 16777216 种摆法，每种还要 O(n²) 检查；加上行列剪枝，实际只访问 2057 个节点。

#include <bits/stdc++.h>
using namespace std;

int n, ans;
int pos[15];                    // pos[i]：第 i 行的棋子放在第几列
bool col[30];                   // 列被占
bool d1[40];                    // i + j 这一族斜线被占
bool d2[40];                    // i - j + n 这一族斜线被占

void dfs(int row) {             // 正在决定第 row 行
    if (row > n) {              // n 行都放好了，得到一个解
        ++ans;                  // 先计数
        if (ans <= 3) {         // 只要前三个解
            for (int i = 1; i <= n; ++i)
                printf("%d%c", pos[i], i == n ? '\n' : ' ');
        }
        return;
    }
    for (int j = 1; j <= n; ++j) {
        // 可行性剪枝：列、两条斜线任意一处冲突，整棵子树都不必进
        if (col[j] || d1[row + j] || d2[row - j + n]) continue;
        pos[row] = j;
        col[j] = d1[row + j] = d2[row - j + n] = 1;     // ① 占三个位置
        dfs(row + 1);                                   // ② 递进
        col[j] = d1[row + j] = d2[row - j + n] = 0;     // ③ 撤这三个
    }
}

int main() {
    cin >> n;
    dfs(1);                    // 从第 1 行开始放
    cout << ans << "\n";       // 第四行：方案总数
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int n, m, ans = 0;
char g[105][105];
int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};    // 八方向：dx 与 dy 必须一一对应
int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};

void dfs(int x, int y) {
    g[x][y] = '.';                          // 标记：直接改图，这一格以后不会再当入口
    for (int k = 0; k < 8; ++k) {
        int nx = x + dx[k], ny = y + dy[k];
        if (nx < 1 || nx > n || ny < 1 || ny > m) continue;   // 先判越界
        if (g[nx][ny] != 'W') continue;     // 只走水
        dfs(nx, ny);
    }
    // 这里没有 g[x][y] = 'W' —— 连通块不撤销
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) cin >> g[i][j];   // cin >> char 会跳过空白，逐字符读正确

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if (g[i][j] == 'W') { ++ans; dfs(i, j); }  // 每发现一个新入口，就多一个水坑

    cout << ans << "\n";
    return 0;
}