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

#define TAILLE		8
#define A		0
#define B		(TAILLE-1)


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


/* //////////////// FILE ET BFS POUR LA VICTOIRE //////////////// */
int suivant[TAILLE * TAILLE] = {0}, debut = 0, fin = 0;

void	push(int n) { suivant[debut++ % TAILLE * TAILLE] = n; }
int	pop(void) { return suivant[fin++ % TAILLE * TAILLE]; }
bool	empty(void) { return (debut %= TAILLE * TAILLE) == (fin %= TAILLE * TAILLE); }

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

	push(A);
	distance[A] = 1;
	while (!empty())
	{
		int s = pop();

		vu[s] = true;
		for (int v = 0; v < TAILLE; v++)
			if (adjacent[s][v] && !vu[v])
			{
				distance[v] = distance[s] + 1;
				push(v);
			}
	}

	printf("\nTABLE DES DISTANCES\n");
	for (int n = 0; n < TAILLE; n++)
		printf("%3d ", distance[n] - 1);
}


int min(int a, int b) { return a < b ? a : b; }
int distance[TAILLE] = {0};


int
dfs(int s)
{
#define INFTY	(1000*1000*1000)

	if (distance[s] == 0)
	{
		distance[s] = INFTY;
		for (int v = 0; v < TAILLE; v++)
			if (adjacent[s][v])
				distance[s] = min(distance[s], dfs(v) + 1);
	}
	return distance[s];
}

/* ////////////////////////////////////////////////////////////// */



int
main(void)
{
	srand(time(NULL));
	for (int _ = rand() % (TAILLE * (TAILLE - 1) / 2); _; --_)
	{
		int x, y;

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

		adjacent[x][y] = true;
	}

	for (int u = 0; u < TAILLE; u++)
	{
		for (int v = 0; v < TAILLE; v++)
			printf("%d ", adjacent[u][v]);
		putchar('\n');
	}
	bfs();

	distance[B] = 1;
	printf("\nDISTANCE A-B: %d\n", dfs(A) - 1);

	return 0;
}
