About Search

about Search

深度优先搜索「一条路走到底，不撞南墙不回头」

  • 深度优先遍历 只要前面有可以走的路，就会一直向前走，直到无路可走才会回头；

  • 「无路可走」有两种情况：① 遇到了墙；② 遇到了已经走过的路；

  • 在「无路可走」的时候，沿着原路返回，直到回到了还有未走过的路的路口，尝试继续走没有走过的路径；有一些路径没有走到，这是因为找到了出口，程序就停止了；

  • 「深度优先遍历」也叫「深度优先搜索」，遍历是行为的描述，搜索是目的（用途）；

  • 遍历不是很深奥的事情，把 所有 可能的情况都看一遍，才能说「找到了目标元素」或者「没找到目标元素」。遍历也称为 穷举，穷举的思想在人类看来虽然很不起眼，但借助 计算机强大的计算能力，穷举可以帮助我们解决很多专业领域知识不能解决的问题。

  • n皇后问题「n个皇后位于nxn的棋盘, 她们不可互相攻击(横 竖 斜 都不可以在一列上)」

  • 解决这个问题的思路是尝试每一种可能，然后逐个判断。只不过回溯算法按照一定的顺序进行尝试，在一定不可能得到解的时候进行剪枝，进而减少了尝试的可能。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class Solution {
    private int n;
    /**
     * 记录某一列是否放置了皇后
     */
    private boolean[] col;
    /**
     * 记录主对角线上的单元格是否放置了皇后
     */
    private boolean[] main;
    /**
     * 记录了副对角线上的单元格是否放置了皇后
     */
    private boolean[] sub;
    
    private List<List<String>> res;

    public List<List<String>> solveNQueens(int n) {
        res = new ArrayList<>();
        if (n == 0) {
            return res;
        }

        // 设置成员变量，减少参数传递，具体作为方法参数还是作为成员变量，请参考团队开发规范
        this.n = n;
        this.col = new boolean[n];
        this.main = new boolean[2 * n - 1];
        this.sub = new boolean[2 * n - 1];
        Deque<Integer> path = new ArrayDeque<>();
        dfs(0, path);
        return res;
    }

    private void dfs(int row, Deque<Integer> path) {
        if (row == n) {
            // 深度优先遍历到下标为 n，表示 [0.. n - 1] 已经填完，得到了一个结果
            List<String> board = convert2board(path);
            res.add(board);
            return;
        }

        // 针对下标为 row 的每一列，尝试是否可以放置
        for (int j = 0; j < n; j++) {
            if (!col[j] && !main[row - j + n - 1] && !sub[row + j]) {
                path.addLast(j);
                col[j] = true;
                main[row - j + n - 1] = true;
                sub[row + j] = true;
                dfs(row + 1, path);
                sub[row + j] = false;
                main[row - j + n - 1] = false;
                col[j] = false;
                path.removeLast();
            }
        }
    }

    private List<String> convert2board(Deque<Integer> path) {
        List<String> board = new ArrayList<>();
        for (Integer num : path) {
            StringBuilder row = new StringBuilder();
            row.append(".".repeat(Math.max(0, n)));
            row.replace(num, num + 1, "Q");
            board.add(row.toString());
        }
        return board;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vis = vector<bool>(n, false);
        tmp = vector<int>(n);
        //从0层递归到n层 ，这里我们无需判断某一层是否有多个皇后，因为我们
        //是按照层来递归，一层只有一个皇后
        dfs(0, n);
        return ans;
    }

    void dfs(int k, const int n){
        //到达n层，存储一个可行解
        if(k == n){
            ans.push_back(vector<string>(n, string(n, '.')));
            for(int i = 0; i < n; i ++)
                ans.back()[i][tmp[i]] = 'Q';
            return ;
        }

        for(int i = 0; i < n; i ++){
            //该列已经有皇后了，不能放置
            if(vis[i])
                continue;
            //第k行第i个位置放皇后
            tmp[k] = i;
            vis[i] = true;
            if(check(k))
                dfs(k + 1, n);
            vis[i] = false;
        }
    }

    //和之前已经放置过的皇后判断是否在对角线、斜对角线上
    bool check(int k){
        for(int i = 0; i < k; i ++){
            if(tmp[i] - i == tmp[k] - k || tmp[i] + i == tmp[k] + k)
                return false;
        }
        return true;
    }

private:
    //判断某一列上是否有皇后
    vector<bool> vis;
    //保存答案
    vector<vector<string>> ans;
    //存储每一层皇后的位置
    vector<int> tmp;
};

DFS的方向模版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
private:
    const int dir[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    int row, column;
public:
    void dfs(vector<vector<int>>& grid, vector<vector<bool>>& vis, int x, int y, int& maxn) {
        if (x < 0 || x >= row || y < 0 || y >= column || vis[x][y] || grid[x][y] == 0) {
            return;
        }
        ++maxn;
        vis[x][y] = true;
        for (int i = 0; i < 4; ++i) {
            int dx = x + dir[i][0];
            int dy = y + dir[i][1];
            dfs(grid, vis, dx, dy, maxn);
        }
#Programming
About Search
https://www.mementos.top/1976/04/01/about Search/
作者
Natsumi
发布于
1976年4月1日
许可协议