ACM►搜索

自动走迷宫（DFS）

功能：

  • 输入一张地图，找出一条可到达终点的路径，1代表不可走，0代表可走，2代表终点。

效果图：

这里写图片描述这里写图片描述

实现原理：

  • 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
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
#include<stdio.h>
typedef struct
{
    int x;
    int y;
    int s;
    int f;
}note;

int map[999][999], book[999][999];
note queue[999];

int main()
{
    int n, i, j, head, tail, x, y, tx, ty, flag;
    int drct[4][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};

    scanf("%d", &n);

    head = 1;
    tail = 1;

    x = 1;
    y = 1;
    //scanf("%d %d", &x, &y);

    queue[tail].x = x;
    queue[tail].y = y;
    queue[tail].s = 0;
    tail++;

    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= n; j++)
        {
            scanf("%d", &map[i][j]);
        }
    }




    while (head < tail)
    {
        for (i = 0; i < 4; i++)
        {
            tx = queue[head].x + drct[i][0];
            ty = queue[head].y + drct[i][1];

            if (tx < 1 || tx > n || ty < 1 || ty > n)
            {
                continue;
            }

            if (map[tx][ty] == 0 && book[tx][ty] == 0)
            {
                book[tx][ty] = 1;

                queue[tail].x = tx;
                queue[tail].y = ty;
                queue[tail].f = head;
                queue[tail].s = queue[head].s + 1;
                //printf("###%d %d\n", tail, queue[tail].f);
                tail++;
            }

            //printf("###%d %d %d %d %d %d\n", tail, queue[tail-1].f, queue[tail - 1].x, queue[tail - 1].y, tx, ty);

            if (map[tx][ty] == 2)
            {
                flag = 1;
                break;
            }
        }

        if (flag == 1)
        {
            break;
        }
        head++;
    }

    if (flag == 1)
    {

    map[tx][ty] = 3;
    for (;;)
    {
        map[queue[head].x][queue[head].y] = 3;
        //printf("%d %d  %d\n", queue[head].x, queue[head].y, i);//
        if(head == 1)
            break;
        head = queue[head].f;
        //getchar();

    }

    putchar('\n');

    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= n; j++)
        {
            if (map[i][j] == 3)
                printf("! ");
            else if (map[i][j] == 1)
                printf("# ");
            else
                printf("* ");
        }
        putchar('\n');
    }

    }

    else
        printf("NO\n");




}

/*
20
0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0
0 1 0 1 0 0 1 0 1 0 0 1 0 1 0 0 1 0 1 0
0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0
0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0
1 0 1 1 0 1 0 1 1 1 1 0 1 1 0 1 0 1 1 1
0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0
0 1 0 1 0 0 1 0 1 0 0 1 0 1 0 0 1 0 1 0
0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 1 1 0 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1
0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0
0 1 0 1 0 0 1 0 1 0 0 1 0 1 0 0 1 0 1 0
0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 1 1 0 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1
0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0
0 1 0 1 0 0 1 0 1 0 0 1 0 1 0 0 1 0 1 0
0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
1 0 1 1 1 1 0 1 1 0 1 0 1 1 1 1 0 1 1 2
*/

PS:

当时刚从啊哈算法上看到DFS，还没实现过，第一次实现写的这东西，也是感兴趣，成就感满满！