diff options
Diffstat (limited to 'maze')
-rw-r--r-- | maze/data_structures.h | 16 | ||||
-rw-r--r-- | maze/point.c | 29 | ||||
-rw-r--r-- | maze/solver.c | 88 |
3 files changed, 133 insertions, 0 deletions
diff --git a/maze/data_structures.h b/maze/data_structures.h new file mode 100644 index 0000000..e856aaa --- /dev/null +++ b/maze/data_structures.h @@ -0,0 +1,16 @@ +#ifndef DATA_STRUCTURES_H +#define DATA_STRUCTURES_H + +struct point { + char c; + int x; + int y; + struct point *next; +}; + +extern struct point *head; + +void push(int x, int y, char c); +char pop(); + +#endif diff --git a/maze/point.c b/maze/point.c new file mode 100644 index 0000000..c83c80d --- /dev/null +++ b/maze/point.c @@ -0,0 +1,29 @@ +#include <stdio.h> +#include <stdlib.h> +#include "data_structures.h" + +struct point *head; + +void +push(int x, int y, char c) +{ + struct point *tmp = malloc(sizeof(struct point)); + tmp->c = c; + tmp->x = x; + tmp->y = y; + tmp->next = head; + head = tmp; +} + +char +pop() +{ + if (head == NULL) { + return -1; + } + struct point *tmp = head; + char c = tmp->c; + head = head->next; + free(tmp); + return c; +} diff --git a/maze/solver.c b/maze/solver.c new file mode 100644 index 0000000..3617f73 --- /dev/null +++ b/maze/solver.c @@ -0,0 +1,88 @@ +#include <stdio.h> +#include <stdlib.h> +#include "data_structures.h" + +int dir[4][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; + +int +walk(struct point maze[7][7], char wall, struct point cur, int vis[7][7], + struct point end) +{ + printf("%d %d ", cur.x, cur.y); + if (maze[cur.y][cur.x].c == wall) { + printf("wall\n"); + return 0; + } + if (vis[cur.y][cur.x]) { + printf("vis\n"); + return 0; + } + if (cur.x == end.x && cur.y == end.y) { + push(end.c, end.x, end.y); + return 1; + } + + printf("\n"); + vis[cur.y][cur.x] = 1; + push(cur.x, cur.y, cur.c); + + for (int i = 0; i < 4; ++i) { + int y = cur.y + dir[i][0]; + int x = cur.x + dir[i][1]; + if (x >= 0 && x < 7 && y >= 0 && y < 7) { + if (walk(maze, wall, maze[y][x], vis, end)) { + return 1; + } + } + } + + pop(cur.c); + + return 0; +} + +void +solve(struct point maze[7][7], char wall, struct point start, struct point end) +{ + int vis[7][7]; + for (int y = 0; y < 7; ++y) { + for (int x = 0; x < 7; ++x) { + vis[y][x] = 0; + } + } + walk(maze, wall, start, vis, end); +} + +int +main() +{ + struct point maze[7][7]; + for (int y = 0; y < 7; ++y) { + for (int x = 0; x < 7; ++x) { + if (x == 0 & y == 0) { + maze[y][x].c = 'S'; + } else if (x == 6 && y == 6) { + maze[y][x].c = 'E'; + } else if (y == 1 && x < 6 + || y == 3 && x > 0 + || y == 5 && x < 6) { + maze[y][x].c = '#'; + } else { + maze[y][x].c = ' '; + } + maze[y][x].x = x; + maze[y][x].y = y; + printf("%c", maze[y][x].c); + } + printf("\n"); + } + solve(maze, '#', maze[0][0], maze[6][6]); + + printf("\n\nreverse solution\n\n"); + struct point *cur = head; + while (cur->next != NULL) { + printf("%d %d\n", cur->x, cur->y); + cur = cur->next; + } + return 0; +} |