Day 19 · DFS 回溯：网格搜索与冲突检测

题意：在 n×n 的棋盘上放 n 个棋子，要求每行、每列都恰好有一个，每条对角线上至多一个。 把所有解按字典序输出前 3 个（每个解输出 n 个数：第 i 个数表示第 i 行的棋子在第几列），最后输出解的总数。

思路

1. 按行放：dfs(i) 表示「现在要给第 i 行放一个皇后」。放完第 n 行就得到一个解。
2. 这一行试每一列：for(j = 1; j <= n; j++)，看第 j 列能不能放。
3. O(1) 判断冲突：col[j] || dg[i+j] || udg[i-j+n] 任意一个为真就跳过（见第 4 节）。
4. 占位 → 递归 → 撤销：放下去就把三个数组标上，dfs(i+1) 之后再全部清零。
5. 输出控制：用一个 total 计数器，只在前 3 个解时打印序列，第 4 行打印总数。

6

2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4

含义：第一个解是「第 1 行放第 2 列、第 2 行放第 4 列、第 3 行放第 6 列……」，6×6 棋盘一共 4 个解。

完整代码

#include <iostream>
using namespace std;

int n, total = 0;
int pos[15];        // pos[i] = 第 i 行的皇后放在第几列
bool col[15];       // col[j]     ：第 j 列有没有被占
bool dg[30];        // dg[i+j]    ：副对角线（右上到左下，i+j 是常数）
bool udg[30];       // udg[i-j+n] ：主对角线（左上到右下，i-j 是常数，+n 是为了不变负数）

void dfs(int i){    // 现在要给第 i 行放皇后
    if(i > n){      // 1~n 行都放好了，得到一个解
        total++;
        if(total <= 3){                  // 只输出前 3 个解
            for(int r = 1; r <= n; r++){
                if(r > 1) cout << " ";
                cout << pos[r];
            }
            cout << "\n";
        }
        return;
    }
    for(int j = 1; j <= n; j++){          // 试着把皇后放在第 j 列
        if(col[j] || dg[i + j] || udg[i - j + n]) continue;   // O(1) 冲突检测
        pos[i] = j;
        col[j] = dg[i + j] = udg[i - j + n] = true;           // 占位
        dfs(i + 1);                                           // 递归下一行
        col[j] = dg[i + j] = udg[i - j + n] = false;          // 回溯：撤销标记
    }
}

int main(){
    cin >> n;
    dfs(1);                    // 从第 1 行开始放
    cout << total << endl;      // 最后一行是解的总个数
    return 0;
}

2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4

易错点

• 三个数组要一起撤销。只撤销 col 忘了撤销对角线，后面分支会被莫名堵死，答案偏少。
• 忘记 +n。udg[i-j] 在 i < j 时下标是负数，直接越界（RE 或玄学错误）。
• 输出格式：数字之间用空格，行末不能有多余空格。用 if(r > 1) cout << " "; 控制。
• 只输出前 3 个解，不是全部解。用计数器 total <= 3 控制，别把 73712 个解全打出来。
• 数组要开够：n 最大 13，所以 col[15] 够用；对角线下标最大到 2n = 26，开 [30] 稳妥。

题意：给一个 N×M 的方格迷宫，里面有 T 个障碍。从起点 (SX,SY) 走到终点 (FX,FY)， 每次只能上下左右走一格，每个方格最多经过一次，问一共有多少种走法。

思路

1. 存地图：读入 N、M、T，然后读起点终点，最后把 T 个障碍点标记成 g[x][y] = 1。
2. 起点先标记：vis[sx][sy] = true;。起点在路径上，也得算「已经走过」。
3. DFS 从起点出发：dfs(x, y) 表示「我现在站在 (x,y) 上」。
4. 终点就是答案 +1：一旦 (x,y) == (fx,fy)，ans++ 然后 return（不用继续走了）。
5. 回溯：四个方向试着走，能走就标记、递归、然后把标记擦掉（这是本题的灵魂）。

2 2 1
1 1 2 2
1 2

1

2×2 的迷宫，(1,2) 是障碍。从 (1,1) 只能先下到 (2,1) 再右到 (2,2)，只有 1 条路。

完整代码

#include <iostream>
using namespace std;

int n, m, t, sx, sy, fx, fy, ans = 0;
int g[10][10];        // g[x][y] = 1 表示这格是障碍
bool vis[10][10];     // 这格走过了没有
int dx[4] = {0, 0, 1, -1};   // ★ 方向数组：行怎么变
int dy[4] = {1, -1, 0, 0};   // ★ 方向数组：列怎么变

void dfs(int x, int y){
    if(x == fx && y == fy){    // 走到终点，找到一条路径
        ans++;
        return;
    }
    for(int d = 0; d < 4; d++){                       // 四个方向逐个试
        int nx = x + dx[d], ny = y + dy[d];
        if(nx < 1 || nx > n || ny < 1 || ny > m) continue;   // 越界（坐标从 1 开始）
        if(g[nx][ny] == 1 || vis[nx][ny]) continue;          // 障碍 或 走过的格子
        vis[nx][ny] = true;      // 进格子：留下脚印
        dfs(nx, ny);             // 继续深入
        vis[nx][ny] = false;      // ★ 出格子：擦掉脚印（回溯）
    }
}

int main(){
    cin >> n >> m >> t;
    cin >> sx >> sy >> fx >> fy;
    for(int i = 0; i < t; i++){
        int x, y;
        cin >> x >> y;
        g[x][y] = 1;             // 标记障碍
    }
    vis[sx][sy] = true;          // 起点也算走过
    dfs(sx, sy);
    cout << ans << endl;
    return 0;
}

易错点

• 忘记回溯（vis[nx][ny] = false;）→ 第一条路径把格子全占了，后面的路径全走不通，答案偏小。
• 忘记标记起点 → 搜索可能绕回起点再走一遍，(1,1)↔(1,2) 之间来回晃，路径数虚高。
• 障碍点在起点上：本题保证不会，但读入顺序要注意——先读起点终点，再读 T 个障碍。
• 越界判断写成 < 0：本题坐标从 1 开始，要用 nx < 1。
• 数组开 [10][10] 时下标能到 9，而 N、M 最大才 5，多出来的空间是留给越界缓冲的。

题意：给一块 N×M 的田地，每格是水（W）或干地（.）。 一个水塘由连通的水格子组成，这里的「相邻」是八邻居（包括斜角）。 问田地里一共有多少个水塘。

思路

这就是第 2 节那个「连通块」任务的模板题，思路非常朴素：

1. 扫一遍全场：从上到下、从左到右看每个格子。
2. 遇到一格还没被处理过的水 W：说明发现了一个新水塘 → 水塘数 +1。
3. 立刻从这格出发 DFS，沿着八个方向把所有能连到的 W 全部「抽干」（改成 .）。
4. 继续扫描：被抽干的格子再也不会被当成「新水塘」，所以每个水塘正好被数一次。

10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.

3

题面说明：共有三个水塘——一个在左上角，一个在左下角，还有一个沿着右侧。

完整代码

#include <iostream>
using namespace std;

int n, m, ans = 0;
char g[105][105];

// ★ 八个方向：左上、上、右上、左、右、左下、下、右下（注意没有 (0,0)）
int dx[8] = {-1, -1, -1,  0, 0,  1, 1, 1};
int dy[8] = {-1,  0,  1, -1, 1, -1, 0, 1};

void dfs(int x, int y){
    g[x][y] = '.';               // 把水抽干，等价于「标记已访问」
    for(int d = 0; d < 8; d++){                 // ★ 这里是 8，不是 4
        int nx = x + dx[d], ny = y + dy[d];
        if(nx < 1 || nx > n || ny < 1 || ny > m) continue;   // 越界
        if(g[nx][ny] == 'W') dfs(nx, ny);                    // 是水就继续扩散
    }
}

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] == 'W'){           // 找到一格还没被抽干的水 → 新水塘
                ans++;
                dfs(i, j);                // 把整个水塘抽干
            }

    cout << ans << endl;
    return 0;
}

易错点

• 方向数组只写了 4 个：斜向相邻的水格会被漏掉，水塘数偏多。这题一定要 8 个。
• 用 cin >> g[i][j] 读字符是可以的（>> 会跳过空白字符）， 但千万不要用 getline 混着读，那样会读到空行。整道题统一用一种读法。
• 标记方式不统一：把 W 改成 . 之后，判断条件必须还是 == 'W'， 别同时又用 vis 数组又改字符，两套状态容易打架。
• 边界 1 ~ n：本题用 1 开始的下标，越界判断是 nx < 1 || nx > n。

题意：给一个 n×n 的字母方阵，里面可能藏着若干个单词 yizhong。 单词沿着八个方向之一连续摆放，摆放过程中不许拐弯。单词之间可以交叉、共用字母。 输出时把不属于任何单词的字母换成 *，属于单词的字母原样保留。

思路

这题和前三题的姿势都不一样：它不是「一步一格地递归」，而是「沿着一个方向一口气走到底」。

1. 找起点：枚举每个格子，只有当它是 y（单词的第一个字母）时才可能是单词的开头。
2. 八个方向各试一次：对每个方向 d，沿着它走 6 步，依次检查第 2~7 个字母是不是 i z h o n g。
3. 越界立刻放弃：走的过程中只要出界，这个方向就作废。
4. 全部对上就标记：把这 7 个格子在 mark 数组里标成 true。
5. 最后统一输出：mark 为真输出原字母，否则输出 *。

7
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa

*******
*******
*******
*******
*******
*******
*******

一个单词都没有 → 全部是星号。

8
qyizhong
gydthkjy
nwidghji
orbzsfgz
hhgrhwth
zzzzzozo
iwdfrgng
yyyygggg

*yizhong
gy******
n*i*****
o**z****
h***h***
z****o**
i*****n*
y******g

第 1 行横着的 yizhong，加上从左上往右下的一条斜线， 两个单词在第 1 行第 2 列的 y 处共用了一个字母。

完整代码

#include <iostream>
#include <string>
using namespace std;

int n;
char g[105][105];
bool mark[105][105];        // mark[x][y] = 这格属于某个 yizhong
string word = "yizhong";

// ★ 八个方向
int dx[8] = {-1, -1, -1,  0, 0,  1, 1, 1};
int dy[8] = {-1,  0,  1, -1, 1, -1, 0, 1};

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

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++){
            if(g[i][j] != word[0]) continue;      // 起点必须是 'y'
            for(int d = 0; d < 8; d++){           // 8 个方向各试一次
                bool ok = true;
                for(int k = 1; k < 7; k++){       // 沿这个方向再走 6 步
                    int nx = i + dx[d] * k, ny = j + dy[d] * k;   // ★ 步长 k
                    if(nx < 1 || nx > n || ny < 1 || ny > n || g[nx][ny] != word[k]){
                        ok = false;
                        break;
                    }
                }
                if(ok)                            // 七个字母全对上了
                    for(int k = 0; k < 7; k++)
                        mark[i + dx[d] * k][j + dy[d] * k] = true;   // 标记这 7 格
            }
        }

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++)
            cout << (mark[i][j] ? g[i][j] : '*');   // 属于单词就印原字母
        cout << "\n";
    }
    return 0;
}

*yizhong
gy******
n*i*****
o**z****
h***h***
z****o**
i*****n*
y******g

易错点

• 边匹配边改字符：应该只做标记、最后统一输出（见上面的 idea 框）。
• 把 k 忘了：写成 i + dx[d] 就变成「只看紧邻的那一格」，永远匹配不上 7 个字母。
• 越界判断漏了一半：行和列都要判，且四个条件用 || 连起来，写成 && 就漏判了。
• 方向数组顺序和 dy 对不上：一旦错位就会「斜着匹配」，样例能过但后面的点全错。
• 单词长度是 7，所以循环写成 k = 1; k < 7（比对后 6 个字母），标记时才是 k = 0; k < 7， 两处的范围不一样，容易写混。