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