January 21, 2022

关于DFS与BFS的学习

前言:关于深度优先搜索和广度优先搜索,莫名又想起了那句话,用空间换取时间。

大部分还是在看别人的文章,自己的见解还不是很足,算法导论上好像有,哪天去看一眼,最先是搜到一篇知乎的文章..那代码写的,血压上来了,还是要一比多家再去认真看文章,算法导论才是标准!

先记录下自己学的,原来是在羊城杯那题需要深度优先搜索,那题并不是经典的走迷宫问题,BFS主要用于最短路径走迷宫,广度优先搜索还没有心情学(最近还有好多加密要手打一份),再干人要坏了。

DFS

这边先记录下对DFS的学习

image-20220122005231203

image-20220122005246569

image-20220122005457938

用着这些思想,打了份走迷宫的DFS(雾)

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <stdio.h>
#include <stdbool.h>

#define ANS_X 2 //坐标
#define ANS_Y 2
#define BOUNDARY_X 3 //地图边界
#define BOUNDARY_Y 3
#define MAX 10

int used[BOUNDARY_X][BOUNDARY_Y] = { 0 }; //已使用坐标
int dir[][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} }; //移动方式
int best[MAX][MAX];

bool DFS(int used[BOUNDARY_X][BOUNDARY_Y], int x, int y);

int main(void)
{
int i, j;

DFS(used, 0, 0);

for ( i = 0; i < MAX; i++ )
{
for ( j = 0; j < MAX; j++ )
{
if ( i == 0 && j == 0 ) //起点
printf("#");
else if ( best[i][j] ) //走过的路
printf("*");
else
printf(" ");
}
printf("\n");
}

return 0;
}

bool DFS(int used[BOUNDARY_X][BOUNDARY_Y], int x, int y)
{
if ( (x == ANS_X) && (y == ANS_Y) )
{
return true; //找到坐标 向上递归(只会发生一次)
}

for ( int i = 0; i <= 4; i++ )
{
int new_x = x + dir[i][0], new_y = y + dir[i][1];//遍历相邻的坐标
if ( new_x >= 0 && new_x < BOUNDARY_X && new_y >= 0 && new_y < BOUNDARY_X && used[new_x][new_y] == 0 )
{

used[new_x][new_y] = 1; //在下一步搜索中 确保当前坐标不会被走到

if ( DFS(used, new_x, new_y) ) //去新坐标找正确坐标
{
printf("(%d,%d)\n", new_x, new_y); //这边找个栈的ADT不错
best[new_x][new_y] = 1; //标记这是走过的路
return true; //向上递归
}

used[new_y][new_x] = 0; //设置成false 因为有可能出现在别的路径中
}
}

return false; //本次搜索无解
}

每次打递归都很兴奋!效果图

image-20220122011415427

笔记未完待续…To be continue–>

https://blog.csdn.net/raphealguo/article/details/7523411

https://blog.csdn.net/raphealguo/article/details/7560918

DASCTF X SU
🍬
HFCTF2022
🍪

About this Post

This post is written by P.Z, licensed under CC BY-NC 4.0.