DFS

算法 > acwing 算法 DFS
发布时间 :
字数:1.9k 阅读 : 评论:
  1. 843. n-皇后问题
    1. 代码：
  • 枚举
    1. 3503. 数组划分
      1. 输入格式
      2. 输出格式
      3. 数据范围
      4. 输入样例：
      5. 输出样例：
      6. 思路：
    2. 1116. 马走日
      1. 题目：
      2. 思路：
      3. 代码：
    3. 1117. 单词接龙
      1. 题目：
      2. 思路：
      3. 代码：
    4. 1118. 分成互质组
      1. 题目：
      2. 思路：
      3. 代码：
    5. 生成全排列
    6. 有重复数字的全排列

    • description: DFS 全称是 Depth First Search，中文名是深度优先搜索，是一种用于遍历或搜索树或图的算法。所谓深度优先，就是说每次都尝试向更深的节点走。

    该算法讲解时常常与 BFS 并列，但两者除了都能遍历图的连通块以外，用途完全不同，很少有能混用两种算法的情况。

    DFS 常常用来指代用递归函数实现的搜索，但实际上两者并不一样。有关该类搜索思想请参阅 DFS（搜索）.

    DFS 最显著的特征在于其 递归调用自身。同时与 BFS 类似，DFS 会对其访问过的点打上访问标记，在遍历图时跳过已打过标记的点，以确保 每个点仅访问一次。符合以上两条规则的函数，便是广义上的 DFS。

    1. 843. n-皇后问题
      1. 代码：
  • 枚举
    1. 3503. 数组划分
      1. 输入格式
      2. 输出格式
      3. 数据范围
      4. 输入样例：
      5. 输出样例：
      6. 思路：
    2. 1116. 马走日
      1. 题目：
      2. 思路：
      3. 代码：
    3. 1117. 单词接龙
      1. 题目：
      2. 思路：
      3. 代码：
    4. 1118. 分成互质组
      1. 题目：
      2. 思路：
      3. 代码：
    5. 生成全排列
    6. 有重复数字的全排列

    • 843. n-皇后问题

    代码：

    #include <iostream>

using namespace std;

const int N = 20;

int n;
char g[N][N];
bool col[N], dg[N], udg[N];

void dfs(int u)
{
    if (u == n)
    {
        for (int i = 0; i < n; i ++ ) puts(g[i]);
        puts("");
        return;
    }

    for (int i = 0; i < n; 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);
            col[i] = dg[u + i] = udg[n - u + i] = false;
            g[u][i] = '.';
        }
}

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

    枚举

    3503. 数组划分

    一个数组中有若干正整数，将此数组划分为两个子数组，使得两个子数组的各元素之和 a,b 的差最小。

    输入格式

    共一行，包含若干个正整数，表示给定数组。

    输出格式

    以降序的顺序，输出两个子数组的各元素之和。

    数据范围

    给定数组的元素个数范围 [2,1000]。
    给定数组的元素取值范围 [1,1000000]。

    输入样例：

    10 20 30 10 10

    输出样例：

    40 40

    思路：

    暴搜，dfs枚举每个数：选或是不选：

    若是当前总和小于总和的一般，则可以选当前数，也可以不选当前数

    否则一定不选当前数。

    注意，dfs枚举一定要有剪枝

    #include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;
int n = 0;
int a[N];
int s, s1;
bool flag = false;

void dfs(int u, int now_sum){
    if(flag)return;
    if(u == n)return;
    if(now_sum <= s / 2){
        s1 = max(s1, now_sum);
        
        //dfs一定要有剪枝操作，否则最后一个样例过不了
        //最后一个样例大概是：有一个特别大的数，其他数加起来都没他大
        //所以当我们遍历到这样的数a[u]，答案一定是[a[u], s - a[u]]
        if(s1 == s / 2)return;
        else if(a[u] > s / 2){
            s1 = s - a[u];
            flag = true;
        }
        
        //选当前的数
        dfs(u + 1, now_sum + a[u]);
    }
    dfs(u + 1, now_sum);
}

int main()
{
    while(cin >> a[n], a[n])s += a[n ++];
    dfs(0, 0);
    cout << s - s1 << " " << s1;
    return 0;
}

    1116. 马走日

    题目：

    马在中国象棋以日字形规则移动。

    请编写一段程序，给定 n∗m 大小的棋盘，以及马的初始位置 (x，y)，要求不能重复经过棋盘上的同一个点，计算马可以有多少途径遍历棋盘上的所有点。

    思路：

    每次走的总步数达到n*m的时候，ans++

    代码：

    #include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10;

int n, m;
bool st[N][N];
int ans;
int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};

void dfs(int x, int y, int cnt)
{
    if (cnt == n * m)
    {
        ans ++ ;
        return;
    }
    st[x][y] = true;

    for (int i = 0; i < 8; i ++ )
    {
        int a = x + dx[i], b = y + dy[i];
        if (a < 0 || a >= n || b < 0 || b >= m) continue;
        if (st[a][b]) continue;
        dfs(a, b, cnt + 1);
    }

    st[x][y] = false;
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T -- )
    {
        int x, y;
        scanf("%d%d%d%d", &n, &m, &x, &y);

        memset(st, 0, sizeof st);
        ans = 0;
        dfs(x, y, 1);

        printf("%d\n", ans);
    }

    return 0;
}

    1117. 单词接龙

    题目：

    单词接龙是一个与我们经常玩的成语接龙相类似的游戏。

    现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”，每个单词最多被使用两次。

    在两个单词相连时，其重合部分合为一部分，例如 beast 和 astonish ，如果接成一条龙则变为 beastonish。

    我们可以任意选择重合部分的长度，但其长度必须大于等于1，且严格小于两个串的长度，例如 at 和 atide 间不能相连。

    思路：

    代码：

    #include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 21;

int n;
string word[N];
int g[N][N];
int used[N];
int ans;

void dfs(string dragon, int last)
{
    ans = max((int)dragon.size(), ans);
    used[last] ++ ;
    for (int i = 0; i < n; i ++ )
        if (g[last][i] && used[i] < 2)
            dfs(dragon + word[i].substr(g[last][i]), i);

    used[last] -- ;
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> word[i];
    char start;
    cin >> start;

    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
        {
            string a = word[i], b = word[j];
            for (int k = 1; k < min(a.size(), b.size()); k ++ )
                if (a.substr(a.size() - k, k) == b.substr(0, k))
                {
                    g[i][j] = k;
                    break;
                }
        }

    for (int i = 0; i < n; i ++ )
        if (word[i][0] == start)
            dfs(word[i], i);

    cout << ans << endl;

    return 0;
}

    1118. 分成互质组

    题目：

    给定 n 个正整数，将它们分组，使得每组中任意两个数互质。

    至少要分成多少个组？

    思路：

    代码：

    #include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
const int N = 10;
int gcd(int x, int y) {
    return y ? gcd(y, x % y) : x;
}
int n, a[N], ans = N, len;
vector<int> g[N];
bool inline check(int u, int c) {
    for (int i = 0; i < g[c].size(); i++)
        if(gcd(g[c][i], u) > 1) return false;
    return true;

void dfs(int u) {
    if(u == n) {
        ans = min(ans, len);
        return;
    }
    for(int i = 0; i < len; i++) {
        if(check(a[u], i)) {
            g[i].push_back(a[u]);
            dfs(u + 1);
            g[i].pop_back();
        }
    }
    g[len++].push_back(a[u]);
    dfs(u + 1);
    g[--len].pop_back();
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", a + i);
    dfs(0);
    printf("%d\n", ans);
}

    生成全排列

    #include <bits/stdc++.h>

using namespace std;

const int N = 15;

vector<vector<int>> res;
int n;
int a[N];
bool st[N];

void dfs(int u){
    if(u == n){    
        vector<int> line;
        for(int i = 0; i < n; i ++){
            line.push_back(a[i]);
        }
        res.push_back(line);
    }
    for(int i = 0; i < n;i ++){
        if(st[i] == false){
            a[u] = i;
            st[i] = true;
            dfs(u + 1);
            st[i] = false;
        }
    }
}


int main(){
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    dfs(0);
    for(int i = 0; i < res.size(); i ++){
        for(int j = 0;j < res[i].size(); j ++){
            cout << res[i][j] << " " ;   
        }
        cout << endl;
    }
    return 0;
}

    有重复数字的全排列

    class Solution {
    public:
    
    vector<vector<int>> res;
    vector<int> path;

    vector<vector<int>> permutation(vector<int>& nums) {
        path.resize(nums.size());
        sort(nums.begin(),nums.end());
        dfs(nums,0,0,0);
        return res;
    }

    void dfs(vector<int> &nums,int u,int start, int state){
        if(u == nums.size()){
            res.push_back(path);
            return;
        }

        if (!u || nums[u] != nums[u - 1]) start = 0;

        for(int i = start;i < nums.size(); i ++){
            if(!(state >> i & 1)){
                path[i] = nums[u];
                dfs(nums,u+1,i+1,state + (1 << i));
            }
        }
    }

};
    转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1149440709@qq.com

    赏

    ©022 张辰琦

    Built with Hexo and 3-hexo theme

    ×

    喜欢就点赞,疼爱就打赏