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

学习编程中的Ben

Hello everyone,欢迎来到 新手必看系列 第二期.因某些人强烈要求,这期决定出 DFS 入门的教程[/s]

还请大家多多欢迎~让我们进入正题吧.

学习编程中的Ben

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

陈尚涵

个人认为这个仅仅只是学到了dfs的思路，还可以进一步进阶，找一些二维的搜索题作为练习巩固（至少我学的时候就是这么学的），二维搜索的学习可以解决很多问题（指暴力）
这里献上二维dfs的模板

1. type dfs(int x, int y, args){ // 根据情况定义类型及其他参数
   
2.         ...; // 特殊情况
   
3.         for (int i = 0; i < len; i++){ // 对每个方向搜索
   
4.                 // 建立新坐标
   
5.                 int xx = x + dx[i];
   
6.                 int yy = y + dy[i];
   
7.                 // 边界/特殊情况=>失败
   
8.                 if (...){
   
9.                         continue;
   
10.                 }
    
11.                 // 防止重复搜索，死循环
    
12.                 vis[xx][yy] = true;
    
13.                 // 成功/抵达/特殊情况
    
14.                 if (...){
    
15.                         ...;
    
16.                         return;
    
17.                 }
    
18.                 dfs(xx, yy, args); // 继续向后搜索
    
19.                 vis[xx][yy] = false;
    
20.         }
    
21. }

复制代码

1101378861

学习一下

shuaiser

加油

陈勃

李志威

感谢感谢

hveagle

向鱼C学习123

good

闪光少年

学习编程中的Ben 发表于 2024-2-4 21:12
@yinda_peng @人造人 @sfqxx @歌者文明清理员 @alwonwang @zhangchenyvn @zhangjinxuan

新年快乐

一只藏狐

感谢讲解

尹玄睿

阿萨德

鱼小二

帖子排版不错滴，中英文标点符号能改进更棒！！

鱼小二

cjjJasonchen

听不懂c/c++ 只会python

人造人

6x6的棋盘有4种情况
我承认这个判断斜角的方法不好，但是我没有好的方法

1. sh-5.2$ cat main.c
   
2. #include <stdio.h>
   
3. #include <stdbool.h>
   
4. 
   
5. void display(bool array[6][6]) {
   
6.     for(size_t y = 0; y < 6; ++y) {
   
7.         for(size_t x = 0; x < 6; ++x) {
   
8.             printf("%d ", array[y][x]);
   
9.         }
   
10.         puts("");
    
11.     }
    
12.     puts("");
    
13. }
    
14. 
    
15. bool check(bool array[6][6]) {
    
16.     for(size_t y = 0; y < 6; ++y) {
    
17.         size_t sum = 0;
    
18.         for(size_t x = 0; x < 6; ++x) {
    
19.             sum += array[y][x];
    
20.         }
    
21.         if(sum > 1) return false;
    
22.     }
    
23.     for(size_t x = 0; x < 6; ++x) {
    
24.         size_t sum = 0;
    
25.         for(size_t y = 0; y < 6; ++y) {
    
26.             sum += array[y][x];
    
27.         }
    
28.         if(sum > 1) return false;
    
29.     }
    
30.     for(size_t y = 0; y < 11; ++y) {
    
31.         size_t sum = 0;
    
32.         for(size_t x = 0, ny = y; x < 6; ++x, ++ny) {
    
33.             if(ny < 5) continue;
    
34.             if(ny >= 11) continue;
    
35.             sum += array[ny - 5][x];
    
36.         }
    
37.         if(sum > 1) return false;
    
38.     }
    
39.     for(size_t y = 0; y < 11; ++y) {
    
40.         size_t sum = 0;
    
41.         for(size_t x = 5, ny = y; x < 6; --x, ++ny) {
    
42.             if(ny < 5) continue;
    
43.             if(ny >= 11) continue;
    
44.             sum += array[ny - 5][x];
    
45.         }
    
46.         if(sum > 1) return false;
    
47.     }
    
48.     return true;
    
49. }
    
50. 
    
51. void chess(bool array[6][6], size_t y) {
    
52.     if(y == 6) {
    
53.         if(check(array)) display(array);
    
54.         return;
    
55.     }
    
56.     for(size_t x = 0; x < 6; ++x) {
    
57.         array[y][x] = true;
    
58.         chess(array, y + 1);
    
59.         array[y][x] = false;
    
60.     }
    
61. }
    
62. 
    
63. int main(void) {
    
64.     bool array[6][6] = {false};
    
65.     chess(array, 0);
    
66.     return 0;
    
67. }
    
68. sh-5.2$ ./main
    
69. 0 1 0 0 0 0
    
70. 0 0 0 1 0 0
    
71. 0 0 0 0 0 1
    
72. 1 0 0 0 0 0
    
73. 0 0 1 0 0 0
    
74. 0 0 0 0 1 0
    
75. 
    
76. 0 0 1 0 0 0
    
77. 0 0 0 0 0 1
    
78. 0 1 0 0 0 0
    
79. 0 0 0 0 1 0
    
80. 1 0 0 0 0 0
    
81. 0 0 0 1 0 0
    
82. 
    
83. 0 0 0 1 0 0
    
84. 1 0 0 0 0 0
    
85. 0 0 0 0 1 0
    
86. 0 1 0 0 0 0
    
87. 0 0 0 0 0 1
    
88. 0 0 1 0 0 0
    
89. 
    
90. 0 0 0 0 1 0
    
91. 0 0 1 0 0 0
    
92. 1 0 0 0 0 0
    
93. 0 0 0 0 0 1
    
94. 0 0 0 1 0 0
    
95. 0 1 0 0 0 0
    
96. 
    
97. sh-5.2$
    

复制代码

人造人

不知道代码对不对，6x6的棋盘有74种情况？

1. #include <stdio.h>
   
2. #include <stdbool.h>
   
3. 
   
4. void display(bool array[6][6]) {
   
5.     for(size_t y = 0; y < 6; ++y) {
   
6.         for(size_t x = 0; x < 6; ++x) {
   
7.             printf("%d ", array[y][x]);
   
8.         }
   
9.         puts("");
   
10.     }
    
11.     puts("");
    
12. }
    
13. 
    
14. bool check(bool array[6][6]) {
    
15.     for(size_t y = 0; y < 6; ++y) {
    
16.         size_t sum = 0;
    
17.         for(size_t x = 0; x < 6; ++x) {
    
18.             sum += array[y][x];
    
19.         }
    
20.         if(sum > 1) return false;
    
21.     }
    
22.     for(size_t x = 0; x < 6; ++x) {
    
23.         size_t sum = 0;
    
24.         for(size_t y = 0; y < 6; ++y) {
    
25.             sum += array[y][x];
    
26.         }
    
27.         if(sum > 1) return false;
    
28.     }
    
29.     for(size_t x = 0; x < 6; ++x) {
    
30.         size_t y = 0;
    
31.         size_t nx = x;
    
32.         size_t sum = 0;
    
33.         while(y < 6 && nx < 6) sum += array[y++][nx--];
    
34.         if(sum > 1) return false;
    
35.     }
    
36.     for(size_t y = 5; y < 6; --y) {
    
37.         size_t ny = y;
    
38.         size_t x = 0;
    
39.         size_t sum = 0;
    
40.         while(ny < 6 && x < 6) sum += array[ny++][x++];
    
41.         if(sum > 1) return false;
    
42.     }
    
43.     return true;
    
44. }
    
45. 
    
46. void chess(bool array[6][6], size_t y) {
    
47.     if(y == 6) {
    
48.         if(check(array)) display(array);
    
49.         return;
    
50.     }
    
51.     for(size_t x = 0; x < 6; ++x) {
    
52.         array[y][x] = true;
    
53.         chess(array, y + 1);
    
54.         array[y][x] = false;
    
55.     }
    
56. }
    
57. 
    
58. int main(void) {
    
59.     bool array[6][6] = {false};
    
60.     chess(array, 0);
    
61.     return 0;
    
62. }
    

复制代码

人造人

1. sh-5.2$ cat main.c
   
2. #include <stdio.h>
   
3. 
   
4. void display(char *buff, size_t count) {
   
5.     for(size_t i = 0; i < count; ++i) {
   
6.         printf("%c", buff[i]);
   
7.     }
   
8.     puts("");
   
9. }
   
10. 
    
11. void permutation(char *buff, size_t index, size_t count) {
    
12.     if(index == count) {
    
13.         display(buff, count);
    
14.         return;
    
15.     }
    
16.     buff[index] = 'N';
    
17.     permutation(buff, index + 1, count);
    
18.     buff[index] = 'Y';
    
19.     permutation(buff, index + 1, count);
    
20. }
    
21. 
    
22. int main(void) {
    
23.     char buff[3];
    
24.     permutation(buff, 0, 3);
    
25.     return 0;
    
26. }
    
27. sh-5.2$ gcc -g3 -Wall -o main main.c
    
28. sh-5.2$ ./main
    
29. NNN
    
30. NNY
    
31. NYN
    
32. NYY
    
33. YNN
    
34. YNY
    
35. YYN
    
36. YYY
    
37. sh-5.2$
    

复制代码

15945179970

陈尚涵

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

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

学习编程中的Ben

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

同意同意,暴力嘿嘿

陈尚涵

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

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

学习编程中的Ben

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

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