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

#define TAILLE	12

typedef struct {
	int	x, y;
} Position;


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

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



/* //////// SUPER FILE MAGIQUE //////// */
Position _file[TAILLE * TAILLE * TAILLE];
int _debut = 0, _fin = 0;
#define P(X,Y)		((Position){.x=X,.y=Y})

void PUSH(Position s)
{
	_file[_debut++ % TAILLE * TAILLE * TAILLE] = s;
}
Position POP(void)
{
	return _file[_fin++ % TAILLE * TAILLE * TAILLE];
}
bool FILE_VIDE(void)
{
	return (_debut %= TAILLE * TAILLE * TAILLE) == (_fin %= TAILLE * TAILLE * TAILLE);
}
/* //////////////////////////////////// */



void bfs(void)
{


	bool vu[TAILLE][TAILLE] = {false};
	int distance[TAILLE][TAILLE];

	vu[0][0] = true;
	distance[0][0] = 0;
	PUSH(P(0, 0));

	while (!FILE_VIDE())
	{
		Position s = POP();
		int dx = 0, dy = 1;

		for (int _ = 0; _ < 4; _++)
		{
			Position v = s;

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

	printf("\nTABLE DES DISTANCES\n");
	for (int x = 0; x < TAILLE; x++)
	{
		printf("  ");
		for (int y = 0; y < TAILLE; y++)
			if (vu[x][y])
				printf("%2d ", distance[x][y]);
			else
				printf(!mur[x][y] ? "   " : " . ");
		putchar('\n');
	}
}

int main(void)
{
	/* « Faux » one-liner pour générer un labyrinthe aléatoire */
	srand(time(NULL));for(int _=rand()%TAILLE*TAILLE/3;_;--_){int x,y;do{x=rand()%TAILLE,y=rand()%TAILLE;}while(mur[x][y]);mur[x][y]=true;}

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

	bfs();

	return 0;
}
