使用EasyX表示DFS深度优先搜索

发表于 更新于 分类于 ，

这是暑假的大作业（为了提前放假，把暑假后所谓“小学期”的课放在期末考试前的周末上！！！还是从早上八点上到下午五点！！！很生气，所以做的也比较粗糙。

使用方法：
1.安装 VisualStdioCommunity
2.安装 EasyX，下载后，将其安装到 VS2022 中。
3.在 VS2022 中新建一个项目，把下面代码复制进去，就可以跑啦！

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
#include <conio.h>
#include <graphics.h>
#include <windows.h>

// save maze
// 0 --> barrier
// 1 --> access
bool maze[8][8] = { 1, 1, 1, 0, 1, 1, 0, 1,
                    1, 1, 1, 0, 0, 1, 1, 1,
                    1, 0, 1, 1, 1, 0, 0, 1, 
                    1, 1, 1, 1, 1, 1, 1, 1,
                    1, 0, 1, 1, 1, 1, 0, 1,
                    1, 1, 1, 0, 1, 1, 1, 1,
                    1, 0, 1, 1, 1, 0, 1, 1,
                    1, 1, 0, 1, 0, 1, 1, 1 };

void drawTable() {
    // setup tangle border
    // leftop(50.50) rightbottom(450,450)
    rectangle(50, 50, 450, 450);
    // draw table
    for (int i = 1; i < 9; i++) line(50, 50 * (i + 1), 450, 50 * (i + 1));
    for (int i = 1; i < 9; i++) line(50 * (i + 1), 50, 50 * (i + 1), 450);
}

void drawStartAndEnd() {
    // add description
    RECT s = { 0, 0, 150, 80 };
    drawtext(_T("Start"), &s, DT_CENTER | DT_VCENTER | DT_SINGLELINE);
    // set start == left top
    solidrectangle(50, 50, 100, 100);
    // add description
    RECT e = { 0, 0, 850, 920 };
    drawtext(_T("End"), &e, DT_CENTER | DT_VCENTER | DT_SINGLELINE);
    // set end
    solidrectangle(400, 400, 450, 450);
}

void drawBarrier() {
    setfillcolor(RED);
    for (int i = 0; i < 8; i++)
        for (int j = 0; j < 8; j++) {
            if (!maze[i][j]) {
                solidrectangle(50 * (j + 1), 50 * (i + 1), 50 * (j + 2),
                    50 * (i + 2));
                Sleep(30);
            }
        }
}

bool visited[8][8];
int dx[4] = { 0, 1, 0, -1 }, dy[4] = { 1, 0, -1, 0 };
void dfs(int sx, int sy) {
    if (sx == 7 && sy == 7) {
        // SUCCESS
        RECT s = { 100, 100, 250, 250 };
        drawtext(_T("YOU WIN!"), &s, DT_CENTER | DT_VCENTER | DT_SINGLELINE);
        Sleep(1000);
        exit(0);
    }

    // visited and draw

    
    for (int i = 0; i < 4; i++) {
        int x = sx + dx[i], y = sy + dy[i];
        // if out of maze or visited or barrier --> continue
        if (x < 0 || x > 7 || y < 0 || y > 7) continue;
        if (visited[x][y] || !maze[x][y]) continue;
        // else next
        visited[sx][sy] = true;
        solidrectangle(50 * (sy + 1), 50 * (sx + 1), 50 * (sy + 2),
            50 * (sx + 2));
        Sleep(500);
        dfs(x, y);
        
        visited[sx][sy] = false;
        clearrectangle(50 * (sy + 1), 50 * (sx + 1), 50 * (sy + 2),
            50 * (sx + 2));
    }
}

int main() {
    // init graph 500 x 500
    initgraph(500, 500);

    drawTable();
    drawStartAndEnd();
    drawBarrier();

    memset(visited, false, sizeof visited);
    setfillcolor(GREEN);
    dfs(0, 0);

    _getch();
    closegraph();
    return 0;
}

其实跑起来是有bug的，visited由bool改为int，再在下方对visited=true改为++，再对每一个visited换一个颜色说不定就好了，不过我太懒了！