#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdbool.h>

#define TAILLE	12
#define MURS	(TAILLE * 4)


bool carte[TAILLE][TAILLE] = {false};




typedef struct {
	int	x, y;
} Position;

Position file[TAILLE * TAILLE * TAILLE];
int debut = 0, fin = 0;

void push(int x, int y) { file[debut++ % TAILLE * TAILLE * TAILLE] = (Position){.x = x, .y = y}; }
Position pop(void) { return file[fin++ % TAILLE * TAILLE * TAILLE]; }
bool empty_queue(void) { return (debut %= TAILLE * TAILLE * TAILLE) == (fin %= TAILLE * TAILLE * TAILLE); }

bool valide(Position p)
{
	return p.x >= 0 && p.x < TAILLE
	    && p.y >= 0 && p.y < TAILLE
	    && !carte[p.x][p.y];
}

int distance[TAILLE][TAILLE];

void
bfs(void)
{
	bool vu[TAILLE][TAILLE] = {false};

	for (int x = 0; x < TAILLE; x++)
		for (int y = 0; y < TAILLE; y++)
			distance[x][y] = -1;

	push(0, 0);
	distance[0][0] = 0;
	vu[0][0] = true;
	while (!empty_queue())
	{
		Position s = pop();
		int dx = 0, dy = 1;

		printf(">> %d "
		for (int _ = 0; _ < 4; _++)
		{
			Position v = s;

			v.x += dx, v.y += dy;
			if (valide(v) && !vu[v.x][v.y])
			{
				distance[v.x][v.y] = distance[s.x][s.y] + 1;
				vu[v.x][v.y] = true;
				push(v.x, v.y);
			}
			dx ^= (-dy), dy = dx ^ (-dy), dx ^= dy;
		}
	}

	printf("\nCARTE DES DISTANCES\n");
	for (int x = 0; x < TAILLE; x++)
	{
		printf("  ");
		for (int y = 0; y < TAILLE; y++)
			if (distance[x][y] == -1)
				printf("  . ");
			else
				printf("%3d ", distance[x][y]);
		putchar('\n');
	}
}


int distance2[TAILLE][TAILLE];

int min(int a, int b) { return a < b ? a : b; }

int
dfs(Position s, int n)
{
#define INFNTY	1000000000


	if (distance2[s.x][s.y] == INFNTY)
	{
		int dx = 0, dy = 1;

		distance2[s.x][s.y] = n;
		for (int _ = 0; _ < 4; _++)
		{
			Position v = s;

			v.x += dx, v.y += dy;
			if (valide(v))
				distance2[s.x][s.y] = min(distance2[s.x][s.y], dfs(v, distance2[s.x][s.y] + 1) + 1);
			dx ^= (-dy), dy = dx ^ (-dy), dx ^= dy;
		}
	}
	return distance2[s.x][s.y];
}



int
main(void)
{
	srand(time(NULL));

	for (int _ = 0; _ < MURS; _++)
	{
		int x, y;

		do
		{
			x = rand() % TAILLE;
			y = rand() % TAILLE;
		} while (carte[x][y]);

		carte[x][y] = true;
	}

	for (int x = 0; x < TAILLE; x++)
	{
		for (int y = 0; y < TAILLE; y++)
			printf("  %c ", carte[x][y] ? '#' : '.');
		putchar('\n');
	}

	bfs();

	for (int x = 0; x < TAILLE; x++)
		for (int y = 0; y < TAILLE; y++)
			distance2[x][y] = INFNTY;

	dfs((Position){.x = 0, .y = 0}, 0);

	printf("\nSORTIE DU DFS\n");
	for (int x = 0; x < TAILLE; x++)
	{
		printf("  ");
		for (int y = 0; y < TAILLE; y++)
			if (distance2[x][y] < INFNTY)
				printf("%3d ", distance2[x][y] == distance[x][y] ? distance[x][y] : -distance2[x][y]);
			else
				printf("  . ");
		putchar('\n');
	}
}
