论坛 › C\C++交流 › 新手必看·DFS快速入门(鱼币~~~)

学习编程中的Ben 发表于 2024-2-4 21:11:18

新手必看·DFS快速入门(鱼币~~~)

本帖最后由 学习编程中的Ben 于 2024-2-4 21:50 编辑


Hello everyone,欢迎来到 新手必看系列 第二期.因某些人强烈要求,这期决定出 DFS 入门的教程
还请大家多多欢迎~让我们进入正题吧.
**** Hidden Message *****
**** Hidden Message *****


求大家给我评点分,谢谢啦~{:10_297:}想到资深鱼油{:10_297:}

@不二如是 @小甲鱼 @Mike_python小 @liuhongrun2022 @陶远航 @陈尚涵 @cjjJasonchen @中英文泡椒

如果有听不懂的地方,或者改进我的帖子的意见,请评论区回复奥

学习编程中的Ben 发表于 2024-2-4 21:12:35

@yinda_peng @人造人 @sfqxx @歌者文明清理员 @alwonwang @zhangchenyvn @zhangjinxuan

陈尚涵 发表于 2024-2-4 21:36:46

本帖最后由 陈尚涵 于 2024-2-4 21:38 编辑

个人认为这个仅仅只是学到了dfs的思路，还可以进一步进阶，找一些二维的搜索题作为练习巩固（至少我学的时候就是这么学的），二维搜索的学习可以解决很多问题（指暴力）
这里献上二维dfs的模板
type dfs(int x, int y, args){ // 根据情况定义类型及其他参数
        ...; // 特殊情况
        for (int i = 0; i < len; i++){ // 对每个方向搜索
                // 建立新坐标
                int xx = x + dx;
                int yy = y + dy;
                // 边界/特殊情况=>失败
                if (...){
                        continue;
                }
                // 防止重复搜索，死循环
                vis = true;
                // 成功/抵达/特殊情况
                if (...){
                        ...;
                        return;
                }
                dfs(xx, yy, args); // 继续向后搜索
                vis = false;
        }
}

sfqxx 发表于 2024-2-4 21:12:34

首楼。

学习编程中的Ben 发表于 2024-2-4 21:13:39

sfqxx 发表于 2024-2-4 21:12
首楼。

评分评分

陶远航 发表于 2024-2-4 21:15:16

没额度了，每天给你评分

学习编程中的Ben 发表于 2024-2-4 21:15:51

陶远航 发表于 2024-2-4 21:15
没额度了，每天给你评分

谢谢啦

学习编程中的Ben 发表于 2024-2-4 21:40:07

陈尚涵 发表于 2024-2-4 21:36
个人认为这个仅仅只是学到了dfs的思路，还可以进一步进阶，找一些二维的搜索题作为练习巩固（至少我学的时 ...

二维的讲解太麻烦了。。。
八皇后那道题目就是二维.但太复杂了

学习编程中的Ben 发表于 2024-2-4 21:40:52

陈尚涵 发表于 2024-2-4 21:36
个人认为这个仅仅只是学到了dfs的思路，还可以进一步进阶，找一些二维的搜索题作为练习巩固（至少我学的时 ...

反正原理一样。把我那几道题做了差不多就掌握了

某一个“天” 发表于 2024-2-4 21:42:35

加油

陈尚涵 发表于 2024-2-4 21:42:43

学习编程中的Ben 发表于 2024-2-4 21:40
二维的讲解太麻烦了。。。
八皇后那道题目就是二维.但太复杂了

我刚学的时候第一道dfs题就是二维{:10_277:}
复杂倒是还好，领悟了的话那确实就领悟了{:10_250:}

某一个“天” 发表于 2024-2-4 21:44:03

确实。应该讲讲题

学习编程中的Ben 发表于 2024-2-4 21:44:34

陈尚涵 发表于 2024-2-4 21:42
我刚学的时候第一道dfs题就是二维
复杂倒是还好，领悟了的话那确实就领悟了

有些新手学习能力没那么强.循序渐进吧

学习编程中的Ben 发表于 2024-2-4 21:45:51

陈尚涵 发表于 2024-2-4 21:42
我刚学的时候第一道dfs题就是二维
复杂倒是还好，领悟了的话那确实就领悟了

如果刚学编程直接上二维不太好吧.
会把人看得头晕.一维能够更快的理解原理
之后多刷题就好了

陈尚涵 发表于 2024-2-4 21:46:32

学习编程中的Ben 发表于 2024-2-4 21:40
反正原理一样。把我那几道题做了差不多就掌握了

这种题中dfs只是一个暴力查找的思路，而二维的思路确实是一样的，但是过程差别很大{:10_250:}
毕竟升维后要考虑的因素会非常多，但是只要掌握了还是很有用的，很多题就可以直接薄纱（指暴力被杀）{:10_282:}
总之即便是二维的dfs也是基础的内容{:10_250:}如果要学习更多的话，还是先学习一下暴力比较好{:10_256:}

学习编程中的Ben 发表于 2024-2-4 21:48:30

陈尚涵 发表于 2024-2-4 21:46
这种题中dfs只是一个暴力查找的思路，而二维的思路确实是一样的，但是过程差别很大
毕竟升维 ...

同意同意,暴力嘿嘿{:10_256:}

陈尚涵 发表于 2024-2-4 21:48:31

学习编程中的Ben 发表于 2024-2-4 21:45
如果刚学编程直接上二维不太好吧.
会把人看得头晕.一维能够更快的理解原理
之后多刷题就好了

二维dfs其实算基础的，毕竟只是个偏分的保利算法，难度嘛，emmm，除了解除死循环的代码外，新手只要认真做了我觉得其他代码可以写出来

15945179970 发表于 2024-2-4 22:37:11

{:5_106:}

人造人 发表于 2024-2-4 23:30:35

sh-5.2$ cat main.c
#include <stdio.h>

void display(char *buff, size_t count) {
    for(size_t i = 0; i < count; ++i) {
      printf("%c", buff);
    }
    puts("");
}

void permutation(char *buff, size_t index, size_t count) {
    if(index == count) {
      display(buff, count);
      return;
    }
    buff = 'N';
    permutation(buff, index + 1, count);
    buff = 'Y';
    permutation(buff, index + 1, count);
}

int main(void) {
    char buff;
    permutation(buff, 0, 3);
    return 0;
}
sh-5.2$ gcc -g3 -Wall -o main main.c
sh-5.2$ ./main
NNN
NNY
NYN
NYY
YNN
YNY
YYN
YYY
sh-5.2$

人造人 发表于 2024-2-5 00:17:00

不知道代码对不对，6x6的棋盘有74种情况？
#include <stdio.h>
#include <stdbool.h>

void display(bool array) {
    for(size_t y = 0; y < 6; ++y) {
      for(size_t x = 0; x < 6; ++x) {
            printf("%d ", array);
      }
      puts("");
    }
    puts("");
}

bool check(bool array) {
    for(size_t y = 0; y < 6; ++y) {
      size_t sum = 0;
      for(size_t x = 0; x < 6; ++x) {
            sum += array;
      }
      if(sum > 1) return false;
    }
    for(size_t x = 0; x < 6; ++x) {
      size_t sum = 0;
      for(size_t y = 0; y < 6; ++y) {
            sum += array;
      }
      if(sum > 1) return false;
    }
    for(size_t x = 0; x < 6; ++x) {
      size_t y = 0;
      size_t nx = x;
      size_t sum = 0;
      while(y < 6 && nx < 6) sum += array;
      if(sum > 1) return false;
    }
    for(size_t y = 5; y < 6; --y) {
      size_t ny = y;
      size_t x = 0;
      size_t sum = 0;
      while(ny < 6 && x < 6) sum += array;
      if(sum > 1) return false;
    }
    return true;
}

void chess(bool array, size_t y) {
    if(y == 6) {
      if(check(array)) display(array);
      return;
    }
    for(size_t x = 0; x < 6; ++x) {
      array = true;
      chess(array, y + 1);
      array = false;
    }
}

int main(void) {
    bool array = {false};
    chess(array, 0);
    return 0;
}

查看完整版本: 新手必看·DFS快速入门(鱼币~~~)