首页
社区
课程
招聘
问答 CTF 排行榜 知识库 工具下载 峰会 看雪商城 证书查询
  1. 社区
  2. CTF对抗
    3. 发新帖
[原创]DFS或BFS地图自动寻路
发表于: 2021-8-12 01:05 8937

[原创]DFS或BFS地图自动寻路

SYJ-Re 活跃值
3
2021-8-12 01:05
8937

标题
一: 步骤总结
二：DFS和BFS
1. DFSAdjacencyMatrix
2. DFSAdjacencyList
3. BFSAdjacencyMatrix
4. 马踏棋盘算法
三：实际CTF案例
示例一：2021cybrics-walker
示例二：2021MTCTF-100mazes
示例三：2021看雪CTF-南冥神功
示例四：2021巅峰极客baby-maze

DFS或BFS地图自动寻路

一：步骤总结

步骤1：找出所有检测点是否合法的限制条件(不是最后的检测，只是检测点是否合法，比如：点不能被访问过，对应坐标上的值不能为负数)

 

步骤2：写出生成所有下一个可能结点列表的函数（利用上面的条件来判断移动之后点是否合法），即得到该顶点的 合法的邻接表(就是所有下一个可能访问的合法点的集合)

 

步骤3：写出dfs，①其实就是找判断dfs成功的条件(可能是路径长度，也可能是其它)，②然后添加该顶点vertex到visited数组或将地图值修改为-1等标记访问过的点的特殊值，③得到该点的合法邻接表，将所有合法邻接点进行递归dfs调用

 

(注意: 如果是走过之后要将地图赋值为一个标记的，而不是用visited数组来记录访问过的点的，就在dfs函数前面添加一句map = map.copy()，避免地图在dfs过程中被修改，path是在dfs递归调用之前进行复制)

 

若题目还有其它要求，添加到递归中即可

二：DFS和BFS

图片描述

1. DFSAdjacencyMatrix

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <stdio.h>
#include <stdlib.h>
/*
邻接矩阵的深度有限递归算法
*/
#define TRUE 1
#define FALSE 0
#define MAX 256
#define INFINITY 65535        // 用65535来代表无穷大
 
typedef struct
{
    char vexs[MAX];                    // 顶点表(一维数组)
    int arc[MAX][MAX];                // 邻接矩阵(二维数组)
    int numVertexes, numEdges;        // 图中当前的顶点数和边数
}MGraph;
 
int visited[MAX];          //定义一个数组来表示点是否被访问过
 
//递归调用进行DFS
void DFS(MGraph* G, int ind)
{
    visited[ind] = TRUE;             //访问过的顶点设置为TRUE
    printf("%c ",G->vexs[ind]);       //打印访问过的顶点
    for(int j=0;j<G->numVertexes;j++)   //遍历邻接矩阵那一行
    {
        if(G->arc[ind][j]==1 && !visited[j])  //对未访问过的邻接顶点进行递归调用
        {
            DFS(G, j);
        }
    }
}
 
void DFSTraverse(MGraph* G)
{
    int i=0;
    //初始化所有点都是未访问状态,就用0,1,2,3...来表示点的标号
    for(i=0;i<G->numVertexes;i++)
    {
        visited[i] = FALSE;
    }
 
    //遍历visited数组,将未访问过的点进行DFS
    //其实DFS(G, 0);即可,没必要弄一个循环
    for(i=0;i<G->numVertexes;i++)
    {
        if(!visited[i])
        {
            DFS(G, i);     //传入没有访问过的点的标号i
        }
    }
}
 
 
 
int main()
{
    //初始化图
    MGraph graph;
    graph.numVertexes = 8;
    graph.numEdges = 9;
    for(int i=0;i<8;i++)
    {
        graph.vexs[i] = 'A' + i;
    }
    int a[8][8]=
        {{0,1,0,1,1,0,0,0},
        {1,0,1,0,1,0,0,0},
        {0,1,0,0,0,1,0,0},
        {1,0,0,0,0,0,1,0},
        {1,1,0,0,0,0,1,0},
        {0,0,1,0,0,0,0,0},
        {0,0,0,1,1,0,0,1},
        {0,0,0,0,0,0,1,0}};
    for(int i=0;i<8;i++)
    {
        for(int j=0;j<8;j++)
        {
            graph.arc[i][j] = a[i][j];
            printf("%d ",graph.arc[i][j]);
        }
        printf("\n");
    }
    DFSTraverse(&graph);
    return 0;
}

2. DFSAdjacencyList

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
67
68
69
70
71
72
73
#include <stdio.h>
#include <stdlib.h>
/*
使用邻接表来进行DFS
*/
#define MAXVEX 100
#define TRUE 1
#define FALSE 0
#define INFINITY 65535        // 用65535来代表无穷大
 
typedef struct EdgeNode            // 边表结点
{
    int adjvex;                    // 邻接点域，存储该顶点对应的下标
    int weight;                    // 用于存储权值，对于非网图可以不需要
    struct EdgeNode *next;        // 链域，指向下一个邻接点
}EdgeNode;
 
typedef struct VertexNode        // 顶点表结点
{
    char data;                    // 顶点域，存储顶点信息
    EdgeNode *firstEdge;        // 边表头指针
}VertexNode, AdjList[MAXVEX];
 
typedef struct
{
    AdjList adjList;
    int numVertexes, numEdges;    // 图中当前顶点数和边数
}GraphAdjList;                  //邻接表
 
int visited[MAXVEX];          //定义一个数组来表示点是否被访问过
 
void DFS(GraphAdjList* GL, int i)
{
    EdgeNode *p;
 
    visited[i] = TRUE;
    printf("%c ", GL->adjList[i].data);
    p = GL->adjList[i].firstEdge;   //找到第一条边准备开始访问
 
    while(p)                   //遍历邻接表(链表)
    {
        if( !visited[p->adjvex] ) //若没被访问过就DFS下去
        {
            DFS(GL, p->adjvex);
        }
        p = p->next;
    }
}
 
// 邻接表的深度遍历操作
void DFSTraverse(GraphAdjList* GL)
{
    int i;
 
    for( i=0; i < GL->numVertexes; i++ )
    {
        visited[i] = FALSE;        // 初始化所有顶点状态都是未访问过状态
    }
 
    for( i=0; i < GL->numVertexes; i++ )
    {
        if( !visited[i] )        // 若是连通图，只会执行一次
        {
            DFS(GL, i);
        }
    }
}
 
int main()
{
    printf("Hello world!\n");
    return 0;
}

3. BFSAdjacencyMatrix

1
2
3
4
5
6
7
8
9
//队列的变化
v0
v1 v3 v4   //这里因为是for循环递增遍历的,所以是v1,v3,v4
v3 v4 v2
v4 v2 v6
v2 v6
v6 v5
v5 v7
v7
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
#include <iostream>
#include <queue>
 
using namespace std;
 
#define MAX 256
//初始化邻接矩阵表示的图
#define vertexnum 8
int matrix[vertexnum][vertexnum] =                  //邻接矩阵
    {{0,1,0,1,1,0,0,0},
    {1,0,1,0,1,0,0,0},
    {0,1,0,0,0,1,0,0},
    {1,0,0,0,0,0,1,0},
    {1,1,0,0,0,0,1,0},
    {0,0,1,0,0,0,0,0},
    {0,0,0,1,1,0,0,1},
    {0,0,0,0,0,0,1,0}};
char vertex[vertexnum] = {'0', '1', '2', '3', '4', '5', '6', '7'};  //顶点
 
//定义一个数组来表示是否被访问过
int visited[vertexnum] = {0};
 
//邻接矩阵实现BFS
void BFS(int ind)
{
    //创建一个队列来准备存放未访问过的顶点
    queue<int> Q;
    if(!visited[ind])      //如果该顶点没被访问就访问它以及它的邻接顶点
    {
        Q.push(ind); //先将该顶点放入到队列中,因为此时该点还未被访问
        visited[ind] = 1;   //设置该顶点的访问标志
 
        //访问该点以及它的邻接点
        while(!Q.empty())
        {
            int tmp = Q.front();
            ind = tmp;
            char ch = vertex[tmp];          //访问队列的最前面一个元素,访问完后弹出队列
            cout << 'v' << ch << " ";
            Q.pop();
 
            for(int j=0;j<vertexnum;j++)    //循环遍历邻接矩阵一行将未访问过的邻接结点加入到队列中去并设置访问标志
            {
                if(matrix[ind][j] && !visited[j])
                {
                    visited[j] = 1;
                    Q.push(j);
                }
            }
        }
    }
}
 
int main()
{
    BFS(0);
    return 0;
}

访问结果：

 

v0 v1 v3 v4 v2 v6 v5 v7

4. 马踏棋盘算法(有点走迷宫的味道了)

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
#include <stdio.h>
#include <time.h>
 
#define X 8
#define Y 8
 
int chess[X][Y];
 
int nextxy(int *x, int *y, int count)   // 找到基于(x,y)位置的下一个可走的位置
{
    switch(count)
    {
        case 0:
            if( *x+2<=X-1 && *y-1>=0 && chess[*x+2][*y-1]==0 )
            {
                *x = *x + 2;
                *y = *y - 1;
                return 1;
            }
            break;
 
        case 1:
            if( *x+2<=X-1 && *y+1<=Y-1 && chess[*x+2][*y+1]==0 )
            {
                *x = *x + 2;
                *y = *y + 1;
                return 1;
            }
            break;
 
        case 2:
            if( *x+1<=X-1 && *y-2>=0 && chess[*x+1][*y-2]==0 )
            {
                *x = *x + 1;
                *y = *y - 2;
                return 1;
            }
            break;
 
        case 3:
            if( *x+1<=X-1 && *y+2<=Y-1 && chess[*x+1][*y+2]==0 )
            {
                *x = *x + 1;
                *y = *y + 2;
                return 1;
            }
            break;
 
        case 4:
            if( *x-2>=0 && *y-1>=0 && chess[*x-2][*y-1]==0 )
            {
                *x = *x - 2;
                *y = *y - 1;
                return 1;
            }
            break;
 
        case 5:
            if( *x-2>=0 && *y+1<=Y-1 && chess[*x-2][*y+1]==0 )
            {
                *x = *x - 2;
                *y = *y + 1;
                return 1;
            }
            break;
 
        case 6:
            if( *x-1>=0 && *y-2>=0 && chess[*x-1][*y-2]==0 )
            {
                *x = *x - 1;
                *y = *y - 2;
                return 1;
            }
            break;
 
        case 7:
            if( *x-1>=0 && *y+2<=Y-1 && chess[*x-1][*y+2]==0 )
            {
                *x = *x - 1;
                *y = *y + 2;
                return 1;
            }
            break;
 
        default:
            break;
    }
 
    return 0;
}
 
void print()                //打印chess棋盘
{
    int i, j;
 
    for( i=0; i < X; i++ )
    {
        for( j=0; j < Y; j++ )
        {
            printf("%2d\t", chess[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}
 
// 深度优先遍历棋盘
// (x,y)为位置坐标
// tag是标记变量，每走一步，tag+1
int TravelChessBoard(int x, int y, int tag)
{
    int x1=x, y1=y, flag=0, count=0;
 
    chess[x][y] = tag;  //tag就是访问的顺序,填写到棋盘对应位置上
 
    // 如果tag==X*Y，表示完成整个棋盘的遍历
    if( tag == X*Y )
    {
        print();  //打印棋盘
        return 1;
    }
 
    //找到马的下一个可走的坐标
    flag = nextxy(&x1, &y1, count);
    while( 0==flag && count < 7 )
    {
        count++;
        flag = nextxy(&x1, &y1, count);
    }
 
    while( flag )
    {
        if( TravelChessBoard(x1, y1, tag+1) )
        {
            return 1;
        }
 
        x1 = x;
        y1 = y;
        count++;
 
        flag = nextxy(&x1, &y1, count);
        while( 0==flag && count < 7 )
        {
            count++;
            flag = nextxy(&x1, &y1, count);
        }
    }
 
    if( 0 == flag )
    {
        chess[x][y] = 0;
    }
 
    return 0;
}
 
int main()
{
    int i, j;
    clock_t start, finish;
 
    start = clock();
 
    for( i=0; i < X; i++ )
    {
        for( j=0; j < Y; j++ )
        {
            chess[i][j] = 0;
        }
    }
 
    if( !TravelChessBoard(2, 0, 1) )
    {
        printf("抱歉，马踏棋盘失败鸟~\n");
    }
 
    finish = clock();
    printf("\n本次计算一共耗时: %f秒\n\n", (double)(finish-start)/CLOCKS_PER_SEC);
 
    return 0;
}

三：实际案例

示例一：2021cybrics-walker

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
67
68
69
70
71
72
73
74
75
# 2021cybrics-walker
# flag格式: cxxxxx...cxxxxx...cxxxxx...cxxxxx...f
# 分析: 一个c后面要接上check函数的5个字符(但是MOV只++一次),就是6个字符,然后之后是路径的其它字符,以此类推下去,总共四个c,最后f结尾
# 我们的地图,看作是一张无向图
our_map = [[0x61, 0xEC, 0xA6, 0x8A, 0x85, 0xF0, 0x97, 0xB5, 0xF5, 0xF3],
        [0x38, 0xEE, 0x26, 0x0A, 0x22, 0x3A, 0x5C, 0x92, 0x8F, 0xA7],
        [0x12, 0xB2, 0x3E, 0x9E, 0x89, 0xC2, 0x4E, 0xA4, 0x9F, 0x96],
        [0x50, 0x45, 0x38, 0xC4, 0x99, 0xA8, 0x5E, 0x97, 0xEA, 0xDC],
        [0xAF, 0xAF, 0xD0, 0xF3, 0xED, 0xF4, 0x2A, 0xA3, 0xA6, 0xD2],
        [0xDE, 0xBB, 0x0A, 0x26, 0x49, 0x74, 0x2C, 0xDB, 0xA1, 0xF6],
        [0xEC, 0x92, 0x2E, 0xC9, 0xD0, 0xFE, 0xE9, 0xF1, 0xA0, 0xE0],
        [0xEC, 0xEE, 0x34, 0x76, 0x3E, 0x08, 0x38, 0x72, 0xA7, 0xF3],
        [0xEE, 0x94, 0xE2, 0xC0, 0xBE, 0xB1, 0xF7, 0x0A, 0xE3, 0xBD],
        [0x66, 0x64, 0x18, 0x08, 0x71, 0x36, 0x7A, 0x5A, 0x9F, 0xB4]]
 
# 比较数据
strings = [[70, 73, 74, 119, 106], [51, 36, 52, 0, 38], [105, 65, 114, 69, 69], [98, 73, 119, 75, 86], [76, 99, 86, 109, 110], [75, 89, 79, 80, 116], [7, 49, 33, 49, 53], [113, 114, 67, 77, 72], [108, 116, 115, 80, 105], [110, 110, 80, 79, 108], [66, 68, 109, 103, 103], [67, 68, 88, 65, 104], [77, 90, 82, 110, 65], [74, 89, 87, 108, 79], [118, 101, 100, 109, 82], [86, 77, 118, 69, 87], [67, 82, 79, 70, 109], [75, 118, 67, 75, 77], [83, 87, 82, 104, 69], [103, 99, 107, 118, 111], [15, 14, 27, 32, 24], [108, 119, 101, 114, 119], [103, 80, 65, 89, 97], [83, 73, 118, 115, 66], [71, 100, 78, 82, 82], [68, 82, 73, 105, 76], [85, 101, 78, 81, 84], [112, 88, 87, 112, 99], [111, 75, 108, 74, 113], [84, 108, 70, 84, 71], [65, 87, 107, 98, 83], [70, 111, 98, 69, 113], [121, 76, 90, 70, 111], [86, 120, 71, 107, 108], [89, 79, 118, 85, 66], [24, 26, 25, 48, 18], [118, 112, 108, 115, 111], [121, 114, 119, 70, 103], [79, 86, 87, 115, 80], [88, 67, 67, 113, 115], [75, 101, 112, 83, 99], [106, 74, 114, 89, 71], [113, 108, 71, 121, 109], [100, 74, 77, 71, 122], [84, 112, 70, 80, 121], [89, 72, 107, 120, 112], [77, 120, 79, 82, 118], [69, 82, 101, 120, 70], [70, 71, 109, 97, 88], [70, 98, 81, 118, 117], [71, 97, 69, 79, 98], [90, 74, 106, 75, 121], [83, 117, 118, 66, 111], [104, 121, 67, 106, 113], [82, 116, 81, 83, 70], [119, 74, 65, 79, 110], [107, 90, 120, 98, 72], [65, 111, 79, 73, 70], [76, 86, 122, 88, 100], [85, 109, 90, 111, 83], [120, 115, 83, 74, 102], [100, 65, 116, 111, 70], [65, 99, 110, 118, 75], [106, 105, 83, 65, 98], [80, 100, 71, 116, 121], [107, 106, 70, 87, 72], [68, 90, 108, 89, 73], [110, 87, 120, 121, 74], [118, 107, 99, 81, 85], [75, 112, 72, 88, 72], [75, 79, 100, 107, 73], [90, 118, 88, 106, 76], [67, 99, 85, 67, 122], [80, 89, 66, 80, 82], [121, 101, 97, 112, 102], [71, 89, 115, 105, 101], [102, 90, 112, 66, 121], [98, 97, 111, 68, 79], [117, 71, 88, 80, 78], [88, 122, 104, 74, 88], [77, 88, 122, 79, 120], [113, 86, 105, 76, 67], [113, 65, 122, 90, 86], [84, 82, 104, 87, 105], [68, 68, 115, 107, 101], [83, 66, 89, 87, 88], [79, 86, 108, 101, 82], [85, 100, 100, 108, 89], [76, 98, 105, 80, 72], [86, 65, 104, 119, 121], [68, 98, 107, 88, 113], [79, 100, 106, 86, 114], [106, 89, 97, 108, 70], [118, 87, 68, 122, 68], [108, 111, 89, 107, 76], [120, 67, 115, 72, 98], [114, 114, 89, 102, 86], [97, 78, 99, 73, 82], [106, 122, 81, 69, 110], [116, 86, 82, 115, 81]]
 
def fuck_check(x, y, mov):                       # CHECK函数的逆向
    xor_data = our_map[x][y]
    cmp_data = strings[mov]
    flag_part = 'c'
    for i in range(5):
        flag_part += chr((cmp_data[i] ^ xor_data) & 0xff)
    return flag_part
 
# 定义一个列表来存放访问过的点
visited = []
 
# 生成传入结点的没遍历过的邻接表(得到没访问过的 该顶点的所有合法邻接点)
# 也相当于遍历邻接矩阵一行之后得到的未访问过的临接点
def find_valid_adjacency_list(x, y):
    adjacency_list = []
    if (x+1 < 10) and ([x+1, y] not in visited) and (our_map[x+1][y] & 0x80 == 0):
        adjacency_list.append((x+1, y, 'd'))
    if (y+1 < 10) and ([x, y+1] not in visited) and (our_map[x][y+1] & 0x80 == 0):
        adjacency_list.append((x, y+1, 'r'))
    if (x-1 < 10) and ([x-1, y] not in visited) and (our_map[x-1][y] & 0x80 == 0):
        adjacency_list.append((x-1, y, 'u'))
    if (y-1 < 10) and ([x, y-1] not in visited) and (our_map[x][y-1] & 0x80 == 0):
        adjacency_list.append((x, y-1, 'l'))
    return adjacency_list
    # 返回该点的合法邻接表
 
# 检查是否是合法字符
def all_see(x):
    for c in x:
        if ord(c) not in range(32, 128):
            return False
    return True
 
def dfs(checkpoint, path, x, y):
    if our_map[x][y] % 2 != 0:
        checkpoint += 1
        part = fuck_check(x, y, len(path)+1)    # 得到那'c'加上之后的5个字符
        if not all_see(part):                   # 检查part是否全部是合法字符
            return
        path.append(part)
        print("checkpoint="+str(checkpoint), "x="+str(x), "y="+str(y))
        if checkpoint == 4:
            print("cybrics{"+"".join(path)+"f}")
            return
 
    # 设置该点到visited数组,表示访问过
    visited.append([x, y])
    # 得到该点的合法邻接表
    valid_list = find_valid_adjacency_list(x, y)
    # 遍历邻接表(里面是合法邻接顶点数组)
    for n in valid_list:
        pathn = path.copy()
        pathn.append(n[2])
        dfs(checkpoint, pathn, n[0], n[1])
 
path0 = []
dfs(0, path0, 0, 0)

示例二：2021MTCTF-100mazes

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
# 2021MTCTF-100mazes
# 走迷宫部分
def checkValid(map, x, y):
    if x < 0 or y < 0 or x > 24 or y > 24:
        return False
    return map[y * 25 + x] == ord('.')
 
def solve(map, startX, startY, direct, path):
    map = map.copy()          # 如果遇见要改变地图的值的,而不是用visited数组的,最好在dfs前面将地图copy一次
    map[startY * 25 + startX] = ord('*')
    if len(path) == 15:       # 用深度来判断是否成功
        return True, path
 
    all_dir = [] # 得到下一个合法的邻接点数组
    if checkValid(map, startX, startY - 1):
        all_dir.append((startX, startY - 1, direct[1]))
    if checkValid(map, startX, startY + 1):
        all_dir.append((startX, startY + 1, direct[2]))
    if checkValid(map, startX - 1, startY):
        all_dir.append((startX - 1, startY, direct[3]))
    if checkValid(map, startX + 1, startY):
        all_dir.append((startX + 1, startY, direct[4]))
 
    pathn = path          # path也要复制一次,避免将错误的添加到了path
    for dir in all_dir:
        result = solve(map, dir[0], dir[1], direct, pathn + dir[2])
        if result[0] == True:
            return result
    return False, ''

这个是曾经归纳的不太好的（仅此纪念一下）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
solve(map, startX, startY, direct, path):
#传入的参数有map,开始位置的坐标,控制方向的字符,和走过的path字符串(path是为了返回的)
 
if len(path) == 15:
    return True, path
#通过走过的路径长度来判断是否返回
 
然后外面还必须有个checkValid来检测走到的位置是否合法
def checkValid(map, x, y):       # 检测某个坐标是否合法
    if x < 0 or y < 0 or x > 24 or y > 24:
        return False
    return map[y * 25 + x] == ord('.')
 
使用checkValid的方法
几个if条件进行判断(也就是查找每一个邻接结点)
根据对应的移动来+-坐标,然后作为参数传入checkValid进行检测,如果这个点合法
就将按照这种移动方法移动的下一个点的坐标和这种移动方法的操作字符都append下来
例:all_dir.append((startX - 1, startY, direct[2]))
 
之后for i in all_dir
逐渐取出所有的可能走的方向,然后进行递归
for dir in all_dir:                         # 这个循环存在的意义是为了避免可以有多条路线
    result = solve(map, dir[0], dir[1], direct, path + dir[2])   
# 递归到下一个点,并将上一个点的方向控制符加到路线中

示例三：2021看雪CTF-南冥神功

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
67
68
69
70
# 2021KCTF-南冥神功
map1 = [0x1, 0x00, 0x01, 0x00, 0x00, 0x01, 0x00, 0x00, 0x01, 0x01, 0x01, 0x01, 0x00, 0x00, 0x01, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x01, 0x01, 0x01, 0x01, 0x01, 0x00, 0x00, 0x01, 0x01, 0x00, 0x01, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x01, 0x00, 0x00, 0x01, 0x01, 0x01, 0x01, 0x00, 0x01, 0x01, 0x01, 0x00, 0x01, 0x00, 0x01, 0x00, 0x00, 0x01, 0x01, 0x01, 0x01, 0x00, 0x01, 0x00, 0x01, 0x00, 0x01, 0x01, 0x00, 0x00, 0x01, 0x00, 0x01, 0x00, 0x01, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x01, 0x01, 0x00, 0x00]
 
def checkValid(theMap, x, y):
    if x < 0 or y < 0:
        return False
    if x > 9 or y > 8:
        return False
    return theMap[y * 10 + x] == 0
 
def isAllClear(theMap):
    return sum(theMap) == 90
 
def genNextValid(theMap, x, y):
    insList = []
    # case1
    if checkValid(theMap, x + 1, y):
        insList.append((1, x + 1, y))
 
    # case4
    if checkValid(theMap, x - 1, y):
        insList.append((4, x - 1, y))
 
    if y % 2 == 0:
        # case2
        if checkValid(theMap, x + 1, y + 1):
            insList.append((2, x + 1, y + 1))
        # default
        if checkValid(theMap, x + 1, y - 1):
            insList.append((-1, x + 1, y - 1))
        # case3
        if checkValid(theMap, x, y + 1):
            insList.append((3, x, y + 1))
        # case5
        if checkValid(theMap, x, y - 1):
            insList.append((5, x, y - 1))
    else:
        # case2
        if checkValid(theMap, x, y + 1):
            insList.append((2, x, y + 1))
        # default
        if checkValid(theMap, x, y - 1):
            insList.append((-1, x, y - 1))
        # case3
        if checkValid(theMap, x - 1, y + 1):
            insList.append((3, x - 1, y + 1))
        # case5
        if checkValid(theMap, x - 1, y - 1):
            insList.append((5, x - 1, y - 1))
    return insList
 
def dfs(CurMap, curX, curY, case_list):
    CurMap = CurMap.copy()          # 要改变地图的,就必须copy一下,避免dfs传址调用过程中把map改了
    CurMap[curY * 10 + curX] = 1
 
    if isAllClear(CurMap):
        print("Find Solve.")
        print(case_list)
        return
 
    curInsList = genNextValid(CurMap, curX, curY)
    if len(curInsList) == 0:
        return None
 
    case_listn = case_list.copy()    # 必须copy一下,避免把错误的值append进了case_list
    for i in curInsList:
        case_listn.append(i[0])
        dfs(CurMap, i[1], i[2], case_listn)
 
dfs(map1, 0, 0, [])

示例四：2021巅峰极客baby-maze

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
from pwn import *
# 定义一个数组来存放访问过的点
visited = []
 
 
# 检测点是否合法
def check_valid(x, y):
    if x < 0 or y < 0:
        return False
    return (x, y) not in visited
 
 
# 得到该顶点的合法邻接表
def find_valid_adjacency_list(x, y):
    arr = []
    if check_valid(x, y+1):
        arr.append(('S', x, y+1))
    if check_valid(x, y-1):
        arr.append(('W', x, y-1))
    if check_valid(x+1, y):
        arr.append(('D', x+1, y))
    if check_valid(x-1, y):
        arr.append(('A', x-1, y))
    return arr
 
 
# 测试路径是否正确
def test(s):
    # print("test:", s)
    p = process("./maze")
    p.recvuntil('Use WASD to navigate, Q to exit\n')
    p.send(s.encode('utf-8'))                                 # 发送要测试的字符串
    lines = []
    for i in range(len(s) + 1):
        line = p.recvline(timeout=1)          # 每次接收一行
        if len(line) == 0:
            p.close()
            return None
        elif b'Oh!!Monster' in line:
            p.close()
            return None
        elif b"I can't see the sky" in line:
            p.close()
            return None
        elif b"nononononono" in line:
            p.close()
            return None
        elif b"Uh... yeah, no." in line:
            p.close()
            return None
        elif b"Let me out!!!" in line:
            p.close()
            return None
        elif b"Fxxk!!!" in line:
            p.close()
            return None
        elif b"Maybe this is a mistack" in line:
            p.close()
            return None
        elif b"Shit!!" in line:
            p.close()
            return None
        elif b"Oh no!!!" in line:
            p.close()
            return None
        elif b"Wall!!!" in line:
            p.close()
            return None
        elif b"OUCH!!!!" in line:
            p.close()
            return None
        elif b"flag" in line:
            print(s)
            raise Exception('you find the flag!!!')
        lines.append(line)
    p.send('Q')
    p.close()
    return "HaHa"
 
 
def bfs(x, y):
    queue = [('S', x, y)]
    visited.append((x, y))
    while len(queue) > 0:
        temp = queue.pop()                                   # 取得队列的第一个元素
        path = temp[0]
        x = temp[1]
        y = temp[2]
        adjacency_list = find_valid_adjacency_list(x, y)     # 生成队列第一个元素顶点的邻接表(合法检测1)
        for n in adjacency_list:                             # 遍历该邻接表
            result = test(path + n[0])                       # (邻接点合法检测2)
            if result != None:                               # 将合法的添加到queue中
                visited.append((n[1], n[2]))                 # 添加到visited列表中
                queue.append((path + n[0], n[1], n[2]))      # 将所有可能顶点都append到queue中
 
 
bfs(0, 0)

图片描述


[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课

最后于 2021-9-14 15:11 被SYJ-Re编辑 ，原因：
收藏
免费 ・4
支持
分享
最新回复 (2)
Taardis
雪    币： 220
能力值： ( LV1，RANK：0 )
在线值：
发帖
回帖
粉丝
私信
2 楼
请问第一个DFS的例子是不是搞错成了BFS的例子？
2021-8-19 12:18
0
SYJ-Re
雪    币： 3668
活跃值： (9335)
能力值： ( LV9，RANK：319 )
在线值：
发帖
回帖
粉丝
私信
3 楼
感谢提醒，贴错了
2021-9-14 15:12
0
游客
登录 | 注册 方可回帖
回帖 表情 雪币赚取及消费
高级回复
返回
//