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
|
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define ROWS 3
#define COLS 3
void
dfs(size_t x, size_t y, char maze[ROWS][COLS], bool visited[ROWS][COLS],
bool cur_path[ROWS][COLS]) {
int dir[4][4] = {
{+0, +1}, // Right.
{+1, +0}, // Down.
{+0, -1}, // Left.
{-1, +0}, // Up.
};
for (int idx = 0; idx < 4; idx++) {
size_t cur_x = x + dir[idx][0];
size_t cur_y = y + dir[idx][1];
// Outn of bounds check.
if (cur_x < 0 || cur_y < 0
|| cur_x > ROWS - 1 || cur_y > COLS - 1)
continue;
if (visited[cur_x][cur_y])
continue;
// Found a solution, exiting.
if (maze[cur_x][cur_y] == '$') {
for (size_t j = 0; j < ROWS; j++) {
for (size_t k = 0; k < COLS; k++) {
if (maze[j][k] == '^' || maze[j][k] == '$')
printf("%c", maze[j][k]);
else {
if (j == cur_x && k == cur_y)
printf("@");
else {
if (cur_path[j][k])
printf("~");
else if (visited[j][k])
printf("-");
else
printf("%c", maze[j][k]);
}
}
printf(" ");
}
printf("\n");
}
exit(0);
}
if (maze[cur_x][cur_y] == '.' || maze[cur_x][cur_y] == '^') {
visited[cur_x][cur_y] = cur_path[cur_x][cur_y] = true;
dfs(cur_x, cur_y, maze, visited, cur_path);
cur_path[cur_x][cur_y] = false;
}
}
}
int
main() {
char maze[ROWS][COLS] = {
{ '^', '.', '.' },
{ '.', '#', '.' },
{ '.', '.', '$' },
};
bool visited[ROWS][COLS] = { false };
bool cur_path[ROWS][COLS] = { false };
visited[0][0] = true;
cur_path[0][0] = true;
dfs(0, 0, maze, visited, cur_path);
}
|