Initial commitHEADmaster

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;
+}