DFS经典问题

发表于 更新于 分类于 ，
本文字数： 2.8k
  • n-皇后问题题解
  • 树的重心问题题解

    n-皇后问题：

题面

n-皇后问题是指将 n 个皇后放在 n∗n 的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。现在给定整数n，请你输出所有的满足条件的棋子摆法。

输入格式

共一行，包含整数n。

输出格式

每个解决方案占n行，每行输出一个长度为n的字符串，用来表示完整的棋盘状态。 其中”.”表示某一个位置的方格状态为空，”Q”表示某一个位置的方格上摆着皇后。 每个方案输出完成后，输出一个空行。

数据范围

1 ≤ n ≤ 9

代码实现：

思路一：按行遍历 O(n!)

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
#include <bits/stdc++.h>

using namespace std;

const int N = 20;// N开20是因为对角线有2N - 1条

bool col[N], dg[N], udg[N];//列 对角线 反对角线

int n;

char g[N][N];

void dfs(int x)
{
    if (x == n)
    {
        for (int i = 0; i < n; i++)
        {
            puts(g[i]);
        }
        puts("");
        return;
    }
    int i = 0;
    for (i = 0; i < n; i++)
    {
        if (!col[i] && !dg[x + i] && !udg[x - i + n]) //x - i + n 给反对角线加偏移量，防止小于0
        {
            g[x][i] = 'Q';
            col[i] = dg[x + i] = udg[x - i + n] = true;
            dfs(x + 1);
            g[x][i] = '.';
            col[i] = dg[x + i] = udg[x - i + n] = false;
        }
    }
}

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;
}

思路二：按元素遍历 O(2的n平方次方)

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
#include <bits/stdc++.h>

using namespace std;

const int N = 20;

bool col[N], dg[N], udg[N], row[N];

int n;

char g[N][N];

void dfs(int x, int y, int s) // s为已经放上去的皇后数
{
    if (y == n)
    {
        y = 0;
        x++;
    }
    if (x == n)
    {
        if (s == n)
        {
            for (int i = 0; i < n; i++)
            {
                puts(g[i]);
            }
            puts("");
        }
        return;
    }
    dfs(x, y + 1, s);
    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] = '.';
    }
}

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;
}

树的重心：

题面

给定一颗树，树中包含n个结点（编号1~n）和n-1条无向边。请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。 重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。

输入格式

第一行包含整数n，表示树的结点数。 接下来n-1行，每行包含两个整数a和b，表示点a和点b之间存在一条边。

输出格式

输出一个整数m，表示重心的所有的子树中最大的子树的结点数目。

数据范围

1≤ n ≤ 1e5

思路：

可以在DFS的过程中创建一个数组将每一个点作为根节点的树的元素的数量和 sum 求出，然后在每一次求 sum 值时求出去掉该点后所有连通块的元素数量的最大值 res（所有子树的元素数量与该点父节点所在的连通块元素数量大小(总元素数 - sum)进行比较），然后再与答案 ans 进行比较，求出最小值

代码实现：

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
#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5 + 10, M = 2 * N;

int h[N], ne[M], e[M], idx; //无向图加边加两条开双倍大小

bool st[N];

int ans = N, n = 0;

void add(int a, int b)
{
    e[++idx] = b;
    ne[idx] = h[a];
    h[a] = idx;
}

int dfs(int u)               //以点u为根节点的子树的大小
{
    st[u] = true;
    int res = 0, sum = 1;    //u点也属于该子树，所以sum初始值为1
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            int s = dfs(j);
            sum += s;
            res = max(res, s);
        }
    }
    res = max(res, n - sum);
    ans = min(res, ans);
    return sum;
}

int main()
{
    memset(h, -1, sizeof h);
    cin >> n;
    for (int i = 0; i < n - 1; i++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    dfs(1);
    cout << ans << endl;
    return 0;
}