/*
 * 1. Trouver la composante connexe reliée à mes bases
 * 2. Affecter une valeur à chaque case de la grille
 * 3. ?????
 * 4. PROFIT!!!!
 *
 * Si de façon improbable l'algorithme termine sous vos yeux,
 * sachez qu'il me reste 11 minutes et je n'ai pas fini de debug.
 */

/* Hack sale contre les timeouts */
#include <time.h>

/* Ne lisez JAMAIS au grand JAMAIS macros.h */
#include "macros.h"



void partie_init(void)
{
}


void dfs(position p, bool vu[39][39])
{
	POUR_CHAQUE_VOISIN(p, v)
		if (est_tuyau(v) && constructeur_tuyau(v) == moi() && !vu[$(v)])
		{
			vu[$(v)] = true;
			dfs(v, vu);
		}
}

void jouer_tour(void)
{
	position parent[39][39], cible[39 * 39];
	bool en_service[39][39] = {false};
	int valeur[39][39] = {0}, cibles = 0;
	clock_t t = clock();


	/* Un premier DFS pour trouver les tuyaux qui nous sont reliés */
	POUR_CHAQUE_BASE(b)
	{
		dfs(b, en_service);
		en_service[$(b)] = true;
	}
	POUR_CHAQUE_BASE_ENNEMIE(b)
		POUR_CHAQUE_VOISIN(b, v)
			if (est_simple_tuyau(v)) detruire(v);

	/*
	 * Un petit BFS pour me porter chance ?
	 * -- Tu veux plaisanter !?
	 */
	INITIALISER_FILE();
	{
		/* On considère les base + mes tuyaux comme points de départ */
		POUR_CHAQUE_CASE(p)
			if (en_service[$(p)])
			{
				valeur[$(p)] = -1;
				ENFILER(p);
			}

		while (!FILE_VIDE())
		{
			position p = DEFILER();

			POUR_CHAQUE_VOISIN(p, v)
				if (!est_pulsar(v) && constructeur_tuyau(p) != adversaire() && valeur[$(v)] == 0)
				{
					TIMEOUT_PROTECTION();
					valeur[$(v)] = valeur[$(p)] - 1;
					parent[$(v)] = p;
					ENFILER(v);
				}
		}
	}


	/* On munit les cases d'une valeur propre */
	POUR_CHAQUE_CASE(p)
		if (est_libre(p) || est_tuyau(p))
		{
			bool interessante = false;

			valeur[$(p)] *= 100;
			POUR_CHAQUE_VOISIN(p, v)
				if (est_pulsar(v))
				{
					pulsar_info pulsar = info_pulsar(v);

					TIMEOUT_PROTECTION();
					interessante = true;
					/*TODO: Trouver les coeffients stœchiométriques */
					valeur[$(p)] += pulsar.puissance * pulsar.pulsations_restantes * 2 / pulsar.periode;
				}

			if (interessante)
			{
				cible[cibles] = p;

				/* On trie par insertion les cibles :p */
				for (int i = cibles++; i > 0 && valeur[$(cible[i])] > valeur[$(cible[i - 1])]; i--)
				{
					ECHANGER(cible[i], cible[i - 1]);
					TIMEOUT_PROTECTION();
				}
			}
		}

	/* Tant qu'on a des points d'action, on remonte les tuyaux */
	for (int i = 0, n = 0; points_action() && i < cibles; i++)
		for (position p = cible[i]; points_action() && !en_service[$(p)]; p = parent[$(p)], n++)
		{
			if (est_libre(p))
				construire(p);
			else if (points_action() && est_simple_tuyau(p) && constructeur_tuyau(p) == moi() && (n % 2))
				ameliorer(p);
			TIMEOUT_PROTECTION();
		}
	/*
	 * On transfère automatiquement et gratuitement la puissance
	 * d'aspiration aux bases en service.
	 */
	position base_donneuse = _(0, 0);

	POUR_CHAQUE_BASE(b)
	{
		bool en_service = false;

		POUR_CHAQUE_VOISIN(b, v)
		{
		    en_service = en_service || est_tuyau(v) || est_super_tuyau(v);
		    TIMEOUT_PROTECTION();
		}

		if (en_service)
			deplacer_aspiration(base_donneuse, b);
		/* À défaut d'être en service, peut-elle se rendre utile ? */
		else if (puissance_aspiration(b) != 0)
			base_donneuse = b;

	}
}


void partie_fin(void)
{
}
