算法-搜索与图论

DFS（深度优先搜索）

八皇后问题

题目链接
对于 DFS 中最经典的八皇后问题，最关键的部分就是判断该坐标是否可以放皇后，以及回溯操作。对于前者，我们从第一行到第 n 行进行 DFS ，因此只用建立列与正反对角线的 vis 数组判定是否符合条件。对于每条正对角线，其 x + y 为定值且唯一；对于反对角线，其 x - y 唯一，为了防止数组下标非负，因此加上 n。最后递归后进行恢复 vis 和撤销皇后即可达到回溯。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void dfs(int u) {
    if(u == n) {
        for(int i = 0; i < n; i ++) {
            for(int j = 0; j < n; j ++) {
                cout << ans[i][j];
            }
            cout << endl;
        }
        cout << endl;
        return;
    }

    for(int i = 0; i < n; i ++) {
        if(!col[i] && !dg[i + u] && !udg[u - i + n]) {
            ans[u][i] = 'Q';
            col[i] = dg[i + u] = udg[u - i + n] = true;
            dfs(u + 1);
            ans[u][i] = '.';
            col[i] = dg[i + u] = udg[u - i + n] = false;
        }
    }
}