acwing算法基础之搜索与图论--DFS

1 基础知识

调用dfs()之后表示已经走到头了，需要往回走了（即，回溯），那这时候就要恢复成调用dfs()之前的模样（即，恢复现场）。

不同的搜索顺序，对应着不同的耗时。

2 模板

题目1：输出1,2,3,…,n的全排列，按照字典序输出。

题目链接为：842排列数字

#include 

using namespace std;

const int N = 10;

int path[N];
bool st[N];

int n;

void dfs(int u) {//第u位填什么
    if (u == n) {
        for (int i = 0; i < u; ++i) {
            cout << path[i] << " ";
        }
        cout << endl;
    }
    
    for (int i = 1; i <= n; ++i) {
        if (!st[i]) {
            path[u] = i;
            st[i] = true;
            dfs(u+1);
            st[i] = false;
        }
    }
    
    return;
}

int main() {
    cin >> n;
    
    dfs(0);
    return 0;
}
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

vector写法如下，

#include 
#include 
#include 

using namespace std;

int main() {
    int n;
    cin >> n;
    
    vector<int> path;
    vector<int> st(n, false);
    
    function<void(int)> dfs = [&](int u) -> void { //第u位填什么
        if (path.size() == n) {
            for (int x : path) {
                cout << x << " ";
            }
            cout << endl;
        }  
        
        for (int i = 0; i < n; ++i) {
            if (!st[i]) {
                path.emplace_back(i + 1);
                st[i] = true;
                dfs(u + 1);
                st[i] = false;
                path.pop_back();
            }
        }
        return;
    };
    
    dfs(0);
    
    return 0;
}
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

题目2：从1,2,3,…,n中选择m个数，考虑选择的数的顺序（即，这是一个排列问题），请按照字典序输出。

#include 

using namespace std;

const int N = 10;

int path[N];
bool st[N];

int n, m;

void dfs(int u) {//第u位填什么
    if (u == m) {
        for (int i = 0; i < u; ++i) {
            cout << path[i] << " ";
        }
        cout << endl;
    }
    
    for (int i = 1; i <= n; ++i) {
        if (!st[i]) {
            path[u] = i;
            st[i] = true;
            dfs(u+1);
            st[i] = false;                
        }
    }
    
    return;
}

int main() {
    cin >> n >> m;
    
    dfs(0);
    return 0;
}
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

题目3：从1,2,3,…,n中选择m个数，不考虑选择的数的顺序（即，这是一个组合问题）。

测试代码的链接：LCR080组合

#include 

using namespace std;

const int N = 10;

int path[N];
bool st[N];

int n, m;

void dfs(int u) {//第u位填什么
    if (u == m) {
        for (int i = 0; i < u; ++i) {
            cout << path[i] << " ";
        }
        cout << endl;
    }
    
    for (int i = 1; i <= n; ++i) {
        if (!st[i]) {
            path[u] = i;
            if (u == 0 || path[u-1] < path[u]) {
                st[i] = true;
                dfs(u+1);
                st[i] = false;                
            }
        }
    }
    
    return;
}

int main() {
    cin >> n >> m;
    
    dfs(0);
    return 0;
}
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

vector格式的代码如下，

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<int> path;
        vector<int> st(n, false);

        vector<vector<int>> res;

        function<void(int)> dfs = [&](int u) -> void { //第u位填什么
            if (path.size() == k) {
                res.emplace_back(path);
            }

            for (int i = 0; i < n; ++i) {
                if (!st[i] && (path.empty() || path.back() < i + 1)) {
                    path.emplace_back(i + 1);
                    st[i] = true;
                    dfs(u + 1);
                    st[i] = false;
                    path.pop_back();
                }
            }
            return;
        };

        dfs(0);
 
        return res;
    }
};
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

题目4：将n个皇后放在n*n的棋盘上，使得n个皇后不能互相攻击到。横、竖、斜线、反斜线。

dfs()方式1：

#include 

using namespace std;

const int N = 20;
char g[N][N];
int col[N], dg[N], udg[N];
int n;

void dfs(int u) {
    if (u == n) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                cout << g[i][j];
            }
            cout << endl;
        }
        cout << endl;
    }
    
    for (int i = 0; i < n; ++i) { //把Q填入到(u,i)位置处
        if (!col[i] && !dg[u+i] && !udg[n-u+i]) {
            g[u][i] = 'Q';
            col[i] = dg[u+i] = udg[n-u+i] = true;
            dfs(u+1);
            g[u][i] = '.';
            col[i] = dg[u+i] = udg[n-u+i] = false;
        }
    }
    return;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            g[i][j] = '.';
        }
    }
    
    dfs(0);
    
    return 0;
}
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

dfs()方式2：

#include 

using namespace std;

const int N = 20;
char g[N][N];
int row[N], col[N], dg[N], udg[N];
int n;

void dfs(int x, int y, int s) {
    if (y == n) {
        y = 0;
        x++;
    }
    
    if (x == n) {
        if (s == n) { //如果有n个皇后，则输出此方案
            for (int i = 0; i < n; ++i) {
                cout << g[i] << endl;
            }
            cout << endl;
        }
        return;
    }
    
    //(x,y)不放皇后
    dfs(x, y + 1, s);
    
    //(x,y)可能放皇后
    if (!row[x] && !col[y] && !dg[x+y] && !udg[x-y+n]) {
        g[x][y] = 'Q';
        row[x] = col[y] = dg[x+y] = udg[x-y+n] = true;
        dfs(x, y + 1, s + 1);
        row[x] = col[y] = dg[x+y] = udg[x-y+n] = false;
        g[x][y] = '.';
    }
    
    return;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            g[i][j] = '.';
        }
    }
    
    dfs(0, 0, 0);
    
    return 0;
}
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

3 工程化

暂无。。。