NO.72十六届蓝桥杯备战|搜索算法-DFS|选数|飞机降落|八皇后|数独(C++)

P1036 [NOIP 2002 普及组] 选数 - 洛谷

组合型枚举，路径⾥⾯记录选择数的「总和」。在选出k 个数之后，判断「是否是质数」

#include <bits/stdc++.h>
using namespace std;

const int N = 25;
int n, k;
int a[N];

int ret;
int path; //记录路径中所选择的数的和

bool isprime(int x)
{
    if (x <= 1) return false;
    //试除法
    for (int i = 2; i <= x / i; i++)
    {
        if (x % i == 0) return false;        
    }
    return true;
}

void dfs(int pos, int begin)
{
    if (pos > k)
    {
        if (isprime(path)) ret++;
        return;
    }
    
    for (int i = begin; i <= n; i++)
    {
        path += a[i];
        dfs(pos+1, i+1);
        path -= a[i];
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    
    dfs(1, 1);
    cout << ret << endl;
    
    return 0;
}

P9241 [蓝桥杯 2023 省 B] 飞机降落 - 洛谷

枚举所有⻜机的「全排列」，判断是否存在⼀种排列，使的全部的⻜机都能安全降落。
剪枝：

• 当前路径⾥⾯只能选没有选过的⻜机；
• 如果这架⻜机不能正常降落，剪掉；
• 如果已经找到⼀种安全降落的⽅式，停⽌枚举，可以通过「递归的返回值」判断是否搜索成功

#include <bits/stdc++.h>
using namespace std;

const int N = 15;

int n;
int t[N], d[N], l[N];
bool st[N];

bool dfs(int pos, int end)
{
    if (pos > n)
    {
        return true;
    }

    for (int i = 1; i <= n; i++)
    {
        if (st[i] == true) continue; //剪枝
        if (end > t[i] + d[i]) continue; //剪枝
        int newend = max(t[i], end) + l[i];
        st[i] = true;
        if (dfs(pos+1, newend)) return true;
        st[i] = false; //恢复现场
    }
    return false;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int T; cin >> T;
    while (T--)
    {
        memset(st, 0, sizeof st);
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> t[i] >> d[i] >> l[i];

        if (dfs(1, 0)) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    
    return 0;
}

P1219 [USACO1.5] 八皇后 Checker Challenge - 洛谷

枚举策略：

• 「⼀⾏⼀⾏」的放皇后：从第⼀⾏开始，尝试在每⼀列上放皇后；
• 如果当前列放上皇后之后「没有冲突」，就标记⼀下这个「放法」，记录⼀下当前⾏的决策，然后「递归」考虑下⼀⾏；
• 等到「所有⾏」都放置完毕之后，输出本次枚举的决策。
  枚举策略应该是⽐较容易想到的，这道题的难点在于如何判断「在这⼀列放上这个皇后之后，是否冲突」。当我们⼀⾏⼀⾏放的时候，「⾏是不会产⽣冲突的」。产⽣冲突的只有「列」，「主对⻆线」，以及「副对⻆线」。我们可以⽤三个数组分别标记：
• col[i] = true ，表⽰第i ⾏放置了⼀个皇后；
• dig1[j - i + n] = true，表⽰y = x + (j - i)这条「主对⻆线」上放置了⼀个皇后；
• dig2[j + i] = true ，表⽰y = -x + (j + i)这条「副对⻆线」上放置了⼀个皇后

#include <bits/stdc++.h>
using namespace std;

const int N = 15;

int n;
bool col[N], st1[N*2], st2[N*2];

int ret;
vector<int> path;

void dfs(int x)
{
    if (x > n)
    {
        ret++;
        if (ret <= 3)
        {
            for (auto x : path) cout << x << " ";
            cout << endl;
        }
        return;
    }

    for (int y = 1; y <= n; y++)
    {
        //判断能不能摆在这一列
        if (col[y] || st1[y-x+n] || st2[x+y]) continue; //剪枝
        col[y] = st1[y-x+n] = st2[x+y] = true;
        path.push_back(y);
        dfs(x+1);
        col[y] = st1[y-x+n] = st2[x+y] = false;
        path.pop_back();
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;

    dfs(1);

    cout << ret << endl;
    
    return 0;
}

P1784 数独 - 洛谷

枚举策略：

• 「⼀个格⼦⼀个格⼦」往⾥⾯填数
• 从第⼀⾏的第⼀个格⼦开始，填上⼀个「没有冲突」的数，然后「递归」到下⼀个格⼦；
• 当某⼀⾏填满之后，递归到「下⼀⾏的起始位置」继续填数。
  可以创建三个数组，⽤来帮助判断填上某⼀个数之后，是否会发⽣冲突。对于3x3⽅格，我们可以给每⼀个格⼦编上号，快读定位。
• row[i][num] = true表⽰：第i ⾏已经放上了num 这个数；
• col[j][num] = true表⽰：第j 列已经放上了num 这个数；
• st[i/3][j/3][num] = true表⽰：[i/3, j/3]的3 × 3 ⽅格⾥，已经放上了num 这个数

#include <bits/stdc++.h>
using namespace std;

int n = 9;
const int N = 10;
int a[N][N];
bool row[N][N], col[N][N], st[N][N][N];

bool dfs(int i, int j)
{
    if (j == n)
    {
        //填满一行后
        i++;
        j = 0;
    }
    if (i == n) return true;

    if (a[i][j]) return dfs(i, j+1);

    for (int x = 1; x <= 9; x++)
    {
        if (row[i][x] || col[j][x] || st[i/3][j/3][x]) continue;   

        row[i][x] = col[j][x] = st[i/3][j/3][x] = true;
        a[i][j] = x;

        if (dfs(i, j+1)) return true;

        row[i][x] = col[j][x] = st[i/3][j/3][x] = false;
        a[i][j] = 0;
    }
    
    return false;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> a[i][j];
            int x = a[i][j];
            if (x)
            {
                //标记
                row[i][x] = col[j][x] = st[i/3][j/3][x] = true;
            }
        }
    }
    
    dfs(0, 0);

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cout << a[i][j] << " ";        
        }
        cout << endl;
    }
    
    return 0;
}