Silencejql
0%

AlgorithmLearning-DFS

发表于 更新于 Valine：
本文字数： 1.5k 阅读时长 ≈ 1 分钟

深度优先

深度优先

示例

XXX + XXX = XXX
将数字1~9分别填入X中,每个数字只能使用一次使得等式成立, 如173+286=459为一组结果, 求总共有多少组. 注:173+286=459与286+173=459为一组.

分析

每个X均有9中可能的数字, 第一个X

1
2
3
4
5
6
int[] result = new int[10];//保存结果
int x = 1;//第几个X
for(int i = 1; i < 10; i++)
{
    result[x] = i;
}

要保证每个数字只能出现一次, 增加标记

1
2
3
4
5
6
7
8
9
10
int[] result = new int[10];//保存结果
bool[] marked = new bool[10];
int x = 1;//第几个X
for(int i = 1; i < 10; i++)
{
    if(marked[i])
        continue;
    result[x] = i;
    marked[i] = true;
}

第二个X与第一个X相同, 将上述封装

1
2
3
4
5
6
7
8
9
10
11
12
void dfs(int x)
{
    for(int i = 1; i < 10; i++)
    {
        if(marked[i])
            continue;
        result[x] = i;
        marked[i] = true;
        dfs(x + 1);
        marked[i] = false;//当每次执行到最后一步后,再返回到前一步填入下一个数 
    }
}

加入返回条件, 计算组数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int steps = 0;
void dfs(int x)
{
    if(x == 10)//总共9个X
    {
        if((result[1] * 100 + result[2] * 10 + result[3]) +
        (result[4] * 100 + result[5] * 10 + result[6]) == 
        (result[7] * 100 + result[8] * 10 + result[9]))
        {
            step++;
            return;
        }
    }
    for(int i = 1; i < 10; i++)
    {
        if(marked[i])
            continue;
        result[x] = i;
        marked[i] = true;
        dfs(x + 1);
        marked[i] = false;//当每次执行到最后一步后,再返回到前一步填入下一个数 
    }
}

代码实现

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
int[] result = new int[10];//保存结果
bool[] marked = new bool[10];
int steps = 0;
void dfs(int x)
{
    if(x == 10)//总共9个X
    {
        //满足条件计数
        if((result[1] * 100 + result[2] * 10 + result[3]) +
        (result[4] * 100 + result[5] * 10 + result[6]) == 
        (result[7] * 100 + result[8] * 10 + result[9]))
        {
            step++;
            return;
        }
    }
    for(int i = 1; i < 10; i++)
    {
        if(marked[i])
            continue;
        result[x] = i;
        marked[i] = true;
        dfs(x + 1);
        marked[i] = false;//当每次执行到最后一步后,再返回到前一步填入下一个数 
    }
}

//Client
dfs(1);
steps /= 2;