diff options
Diffstat (limited to 'maze/solver.c')
-rw-r--r-- | maze/solver.c | 88 |
1 files changed, 88 insertions, 0 deletions
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; +} |