/**
 * Principe général de l'IA :
 * 
 * A chaque tour, mon IA traite chaque agent un par un de la même
 * manière.
 * Pour chaque agent :
 * - s'il y a un manchot éjectable sur une case contenant un alien qui
 *   rapporte plus que le nôtre, l'éjecter
 * - détermination des distances (nb. tours + points d'actions du
 *   dernier tour) minimales pour atteindre chaque case avec Dijkstra
 * - attribution d'un score à chaque case, score qui favorise les cases
 *   contenant un alien au tour actuel/peu après l'arrivée à cette case
 *   et les cases permettant d'éjecter un agent adverse de son alien,
 *   score qui décroît en fonction du nombre de tours à attendre avant que
 *   l'alien n'arrive
 * - choix de la case au score le plus élevé, déplacement tant que
 *   possible
 * - pousser quelqu'un si possible sans attendre le prochain tour
 * 
 * Algorithme utilisé : Dijkstra
 * Stratégie employée : heuristique (?)
 * 
 * Idées n'ayant pas abouti : 
 * - Toute manière de faire coopérer des manchots de mon équipe
 * (ex: empêcher les éjections par l'adversaire)
 * - Tout changement dans la fonction attribuant les points par case
 * après la version 76 (je suis allé jusqu'à 82)
 * - Privilégier les "coins" (c'est-à-dire les cases dont les manchots
 * ne peuvent pas être poussés)
 * 
 * Ce que j'aurais aimé faire si j'avais plus de temps :
 * - Coopération entre les manchots !
 * - Tri entre les aliens selon leur score
 * - Ejection moins systématique des manchots adverses
 * - Amélioration générale de l'heuristique après observation de
 * matchs
 */



#include "prologin.hh"
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;



/// Fonctions/variables/structures/constantes utilitaires
/// Association des valeurs de l'enum direction aux opérations lig/col
struct Deplacement {
	int dlig, dcol;
	direction direct;
};

const int INFINI = 2*1000*1000*1000;
const Deplacement DEPLACEMENTS[] = {{0,1,EST}, {1,0,SUD}, {0,-1,OUEST}, {-1,0,NORD}};
int maxPoints = 0; /// l'alien qui rapporte le + de points
/// Stocke les aliens présents ou futurs par case
vector<vector<alien_info > > aliens(TAILLE_BANQUISE, vector<alien_info > (TAILLE_BANQUISE, {{-1,-1},-1,-1,-1,-1}));

/// Outils
bool dansGrille(position pos) {
	return pos.ligne >= 0 && pos.ligne < TAILLE_BANQUISE && pos.colonne >= 0 && pos.colonne < TAILLE_BANQUISE;
}

bool libre(position pos) {
	return type_case(pos) == LIBRE && agent_sur_case(pos) == -1;
}

position appliquerDepl(position pos, int iDepl) {
	return {pos.ligne+DEPLACEMENTS[iDepl].dlig, pos.colonne+DEPLACEMENTS[iDepl].dcol};
}




/** 
 * Une situation pour le dijkstra : la position de départ de l'agent
 * étant fixée et étant donné une case, combien de tours et de PA
 * (au dernier tour) il faut pour l'atteindre, et quelle est la case 
 * précédente (pour retrouver le chemin)
 */
struct Situation {
	position caze, precedent;
	int nbTours,pa; /// pa = points d'action
	
	Situation(): caze({-1,-1}), precedent({-1,-1}), nbTours(-1), pa(-1) {}
	Situation(position caze, position precedent, int nbTours, int pa): caze(caze), precedent(precedent), nbTours(nbTours), pa(pa) {}
	
	
	/// Tri par nombre de tours nécessaires puis par points d'action supplémentaires
	bool operator<(const Situation &autre) const {
		if(nbTours != autre.nbTours)
			return nbTours < autre.nbTours;
		else
			return pa < autre.pa;
	}
	
	bool operator>(const Situation &autre) const {
		if(nbTours != autre.nbTours)
			return nbTours > autre.nbTours;
		else
			return pa > autre.pa;
	}
	
	/// Pour le Dijkstra, calcul des situations voisines par glissade ou déplacement
	vector<Situation> suivants() {
		vector<Situation> ret;
		/// Déplacement
		for(int iDepl = 0; iDepl < 4; iDepl++) {
			position posSuiv = appliquerDepl(caze, iDepl);
			if(libre(posSuiv)) {
				int nbToursS = nbTours, paS = pa+COUT_DEPLACEMENT;
				/// Gestion d'une action qui déborde sur le tour suivant
				if(paS >= NB_POINTS_ACTION) {
					nbToursS ++;
					paS %= NB_POINTS_ACTION;
				}
				ret.push_back(Situation(posSuiv, caze, nbToursS, paS));
			}
		}
		
		/// Glissade
		for(int iDepl = 0; iDepl < 4; iDepl++) {
			position posFin = caze;
			while(libre(appliquerDepl(posFin, iDepl)))
				posFin = appliquerDepl(posFin, iDepl);
			int nbToursS = nbTours, paS = pa+COUT_GLISSADE;
			/// Gestion d'une action qui déborde sur le tour suivant
			if(paS >= NB_POINTS_ACTION) {
				nbToursS ++;
				paS %= NB_POINTS_ACTION;
			}
			ret.push_back(Situation(posFin, caze, nbToursS, paS));
		}
		return ret;
	}
};


/// Structure pour stocker des résultats de dijkstra
struct ResultatsRecherche {vector<Situation> positions; vector<vector<Situation> > distances;};

/// Fonction qui effectue le Dijkstra à partir d'un agent
ResultatsRecherche positionsAtteignables(int qui, int iAgent) {
	vector<Situation> ret;
	/// On stocke pour toute case non visitée une Situation dont tous les champs sont à -1
	vector<vector<Situation> > visite(TAILLE_BANQUISE, vector<Situation> (TAILLE_BANQUISE, Situation()));
	priority_queue<Situation, vector<Situation>, greater<Situation> > file;
	/// La case de départ est à distance 0 et n'a pas de précédente case
	file.push({position_agent(qui, iAgent), {-1,-1}, 0, 0});
	while(!file.empty()) {
		Situation sit = file.top();
		file.pop();
		if(visite[sit.caze.ligne][sit.caze.colonne].nbTours != -1)
			continue;
		ret.push_back(sit);
		visite[sit.caze.ligne][sit.caze.colonne] = sit;
		for(Situation suivant : sit.suivants())
			if(visite[suivant.caze.ligne][suivant.caze.colonne].nbTours == -1) /// si non déterminé
				file.push(suivant);
	}
	return {ret, visite};
}

/// Retrouve le chemin menant à une case depuis l'agent. 
/// Attention : front() = arrivée, back() = départ
vector<Situation> cheminVers(ResultatsRecherche resultats, int ou) {
	vector<Situation> ret;
	Situation posActuelle = resultats.positions[ou];
	ret.push_back(posActuelle);
	while(posActuelle.precedent.ligne >= 0) { /// négatif = indéfini
		posActuelle = resultats.distances[posActuelle.precedent.ligne][posActuelle.precedent.colonne];
		ret.push_back(posActuelle);
	}
	return ret;
}

/// Calcule le nombre de tours nécessaires pour entièrement terminer un chemin;
/// y compris le premier et le dernier.
pair<int,int> nbToursNecessaires(vector<Situation> chemin) {
	return make_pair(chemin.front().nbTours, chemin.front().pa);
}

/// Effectue un déplacement ou une glissade de pos1 à pos2.
erreur effectuerDepl(int iAgent, position pos1, position pos2) {
	int distManhattan = abs(pos1.ligne-pos2.ligne) + abs(pos1.colonne-pos2.colonne);
	if(distManhattan == 1) { /// les deux cases sont côte à côte
		if(pos1.ligne-1 == pos2.ligne)
			return deplacer(iAgent, NORD);
		else if(pos1.ligne+1 == pos2.ligne)
			return deplacer(iAgent, SUD);
		else if(pos1.colonne-1 == pos2.colonne)
			return deplacer(iAgent, OUEST);
		else
			return deplacer(iAgent, EST);
	}
	else { /// les deux sont dans une ligne droite mais distants de plus d'une case
		if(pos1.ligne < pos2.ligne)
			return glisser(iAgent, SUD);
		else if(pos1.ligne > pos2.ligne)
			return glisser(iAgent, NORD);
		else if(pos1.colonne < pos2.colonne)
			return glisser(iAgent, EST);
		else
			return glisser(iAgent, OUEST);
	}
}

/// Cherche un adversaire à pousser, en priorité un adversaire sur un alien.
/// Le bool indique si c'est possible ou non, la direction... dans quelle direction.
pair<bool,direction> dirPousser(position caze) {
	for(int alienFacultatif = 0; alienFacultatif < 2; alienFacultatif++)
		for(int iDir = 0; iDir < 4; iDir++) {
			position suiv = appliquerDepl(caze, iDir);
			if(dansGrille(suiv) && agent_sur_case(suiv) == adversaire() && (alienFacultatif == 1 || alien_sur_case(suiv))) {
				int dist = 0;
				while(libre(appliquerDepl(suiv, iDir))) {
					suiv = appliquerDepl(suiv, iDir);
					dist++;
				}
				if(dist > 0 && !alien_sur_case(suiv)) /// il est possible de le pousser
					return make_pair(true, DEPLACEMENTS[iDir].direct);
			}
		}
	/// impossible de pousser qui que ce soit, donc
	return make_pair(false,NORD);
}

/// Détermine si un manchot sera attrapé si rien ne se passe (agent immobile)
bool seraAttrappe(position caze) {
	if(!alien_sur_case(caze))
		return false;
	alien_info alien = info_alien(caze);
	return tour_actuel()+NB_TOURS_CAPTURE-alien.capture_en_cours <= alien.tour_invasion+alien.duree_invasion;
}

/// Retourne si une case est un coin (un manchot dans cette case est impoussable).
/// Ne prend pas en compte les manchots.
bool estCoin(position caze) {
	bool b[2] = {false}; /// horizontal et vertical, voir tableau DEPLACEMENTS
	for(int dir = 0; dir < 4; dir ++) {
		position suiv = appliquerDepl(caze, dir);
		if(dansGrille(suiv) && type_case(suiv) == MUR)
			b[dir%2] = true;
	}
	return b[0] && b[1];
}

/// Retourne le nomber de manchots adverses adjacents à une case donnée et
/// qui peuvent pousser un manchot de la case
int nbDangers(position caze) {
	int ret = 0;
	for(int dir = 0; dir < 4; dir++) {
		position chercheAgent = appliquerDepl(caze, dir), chercheVide = appliquerDepl(caze, (dir+2)%4);
		if(agent_sur_case(chercheAgent) == adversaire() && libre(chercheVide))
			ret++;
	}
	return ret;
}



/**
 * Cette fonction attribue un score à chaque case après le Dijkstra.
 * 
 * Attribue 10 000 000 aux cases où se trouve déjà l'agent et où il est
 * en train de capturer un alien positif, -10 000 000 dans le cas d'un alien
 * négatif (!). Cette manière d'attribuer des cases devrait permettre de tolérer
 * un séjour d'un tour sur un alien négatif (ex: pour pousser).
 * 
 * Calcule une attente, qui correspond au temps avant l'arrivée de l'alien.
 * 
 * Attribue environ 90 000 aux cases où, dans le futur ou dans le présent,
 * se trouve(ra) un alien que l'agent peut attrapper avant que l'alien
 * ne reparte. Le score attribué à ces cases décroît avec le nombre de
 * tours nécessaires pour les atteindre.
 * 
 * Attribue environ 90 000 aux cases depuis lesquelles l'agent peut éjecter
 * un agent adverse de son alien. La règle d'attribution des points est
 * similaire à celle pour les cases avec aliens (il suffit de se déplacer
 * vers la case avec alien ensuite).
 * J'ai tenté avec plus ou moins de succès de prendre en compte la "taille"
 * de l'alien, le nombre de points d'action de marge restants (pourquoi ???),
 * le fait que la case soit un coin ou non, et la possibilité d'être immédiatement
 * éjecté.
 * 
 * Attribue 0 dans les autres cas.
 */
int scoreCase(int iPos, int iAgent, ResultatsRecherche resultats) {
	position caze = resultats.positions[iPos].caze;
	/// Capture en cours
	if(caze == position_agent(moi(),iAgent) && alien_sur_case(caze))
		return 10000000 * (info_alien(caze).points_capture < 0 ? -1 : 1);
	
	vector<Situation> chemin = cheminVers(resultats, iPos);
	pair<int,int> nbTours = nbToursNecessaires(chemin);
	int tourArrivee = tour_actuel()+nbTours.first-1;
	int paRestant = NB_POINTS_ACTION - nbTours.second;
	int scoreAlien = -1;
	alien_info alien = aliens[caze.ligne][caze.colonne];
	int attente = max(0, alien.tour_invasion-tourArrivee);
	
	/// Case avec alien présent/futur
	if(alien.tour_invasion >= 0) {
		int dernierTourAlien = alien.tour_invasion+alien.duree_invasion-1;
		if(tourArrivee+2 <= dernierTourAlien) {
			scoreAlien = 
				90000
				/max(1,attente)
				+(double)alien.points_capture/maxPoints*10
				+paRestant
				+ (estCoin(alien.pos) ? 100 : 0)
				- nbDangers(alien.pos)*100;
		}
	}
	
	/// Case permettant d'éjecter un agent adversaire
	if(paRestant < COUT_POUSSER) {
		attente++; /// j'ignore pourquoi ce ++, mais presque toute modification entraîne une chute du score
	}
	if(tourArrivee != tour_actuel() || paRestant >= COUT_POUSSER) /// pour éviter de se faire éjecter tout de suite
		for(int dir = 0; dir < 4; dir++) {
			position suiv = appliquerDepl(caze, dir);
			if(agent_sur_case(suiv) == adversaire() && seraAttrappe(suiv) && libre(appliquerDepl(suiv, dir)))
				scoreAlien = 
					90000
					/max(1,attente)
					+(double)alien.points_capture/maxPoints*10
					+paRestant
					+ (estCoin(alien.pos) ? 100 : 0)
					- nbDangers(alien.pos)*100;
		}
	
	/// Les scores négatifs sont réservés aux aliens négatifs
	int ret = max(0, scoreAlien - nbTours.first*100 - nbTours.second);
	return ret;
}


/**
 * Fonction qui essaie d'éjecter un manchot adverse qui serait sur un
 * alien qui rapporte plus que celui de l'agent iAgent (une absence
 * d'alien rapportant 0).
 */
void ejecterDanger(int iAgent) {
	position pos = position_agent(moi(), iAgent);
	int valeurAlien = 0;
	alien_info alienCase = info_alien(pos);
	if(seraAttrappe(pos))
		valeurAlien = alienCase.points_capture;
	for(int dir = 0; dir < 4; dir++) {
		position suiv = appliquerDepl(pos, dir);
		/// glisser jusqu'à l'éventuel manchot
		while(type_case(suiv) == LIBRE && agent_sur_case(suiv) == -1)
			suiv = appliquerDepl(suiv, dir);
		if(agent_sur_case(suiv) == adversaire() && alien_sur_case(suiv)) {
			int valeurNv = 0;
			if(seraAttrappe(suiv))
				valeurNv = info_alien(suiv).points_capture;
			/// On ne considère pas les manchots adverses qui capturent un moins bon alien
			if(valeurNv < valeurAlien || (valeurAlien == valeurNv && valeurNv == 0))
				continue;
			
			/// Vérification de la possibilité de pousser
			position derriere = appliquerDepl(suiv, dir);
			if(type_case(derriere) == LIBRE && agent_sur_case(derriere) == -1) {
				/// Glisser ou se déplacer, selon les PA demandés
				int dist = abs(suiv.ligne-pos.ligne)+abs(suiv.colonne-pos.colonne)-1;
				if(dist < 3)
					for(int i = 0; i < dist; i++)
						deplacer(iAgent, DEPLACEMENTS[dir].direct);
				else
					glisser(iAgent, DEPLACEMENTS[dir].direct);
				pousser(iAgent, DEPLACEMENTS[dir].direct);
				deplacer(iAgent, DEPLACEMENTS[dir].direct);
				return;
			}
		}
	}
}





/// Fonction appelée au début de la partie. Stocke les aliens de toute la
/// partie par case (le sujet précise qu'ils sont uniques par case).
void partie_init(){
	vector<alien_info> infos = liste_aliens();
	for(alien_info alien : infos)
		if(alien.duree_invasion >= 3) {
			aliens[alien.pos.ligne][alien.pos.colonne] = alien;
			maxPoints = max(maxPoints, alien.points_capture);
		}
}



/// Fonction appelée à chaque tour.
void jouer_tour()
{
	/// MàJ du tableau des aliens
	for(int l = 0; l < TAILLE_BANQUISE; l++)
		for(int c = 0; c < TAILLE_BANQUISE; c++)
			/// Si l'alien est disparu, l'effacer
			if(aliens[l][c].tour_invasion >= 0 && aliens[l][c].tour_invasion <= tour_actuel() && !alien_sur_case({l,c}))
				aliens[l][c] = {{-1,-1},-1,-1,-1,-1};
				
	
	for(int iAgent = 0; iAgent < NB_AGENTS; iAgent++) {		
		/// Agressivité ! Ejection de tout manchot adverse en train de
		/// capturer un alien, si possible dans ce tour
		ejecterDanger(iAgent);
		
		/// Détermination meilleure case (score maximal). Parcours par
		/// distance croissante du fait du Dijkstra.
		ResultatsRecherche resultats = positionsAtteignables(moi(), iAgent);
		int scoreMax = 0, iCorres = 0;
		for(int i = 0; i < (int)resultats.positions.size(); i++) {
			int score = scoreCase(i, iAgent, resultats);
			if(score > scoreMax) {
				scoreMax = score;
				iCorres = i;
			}
		}
		
		/// Parcours du chemin vers la meilleure case, autant que possible
		/// pour ce tour
		vector<Situation> chemin = cheminVers(resultats, iCorres);
		
		/// Debug
		for(Situation sit : chemin)
			debug_afficher_drapeau(sit.caze, DRAPEAU_BLEU);
		debug_afficher_drapeau(chemin[0].caze, DRAPEAU_VERT);
		
		
		if(chemin.size() > 1) {
			int nbFaits = 0;
			for(int i = chemin.size()-2; i >= 0; i--) {
				erreur ret = effectuerDepl(iAgent, chemin[i+1].caze, chemin[i].caze);
				if(ret != OK)
					break;
				else
					nbFaits++;
			}
		}
		
		/// Agressivité bis : pousser quelqu'un si possible
		pair<bool,direction> pousse = dirPousser(position_agent(moi(), iAgent));
		if(pousse.first)
			pousser(iAgent, pousse.second);
		
		/// Effacement des drapeaux de débug
		for(Situation sit : chemin)
			debug_afficher_drapeau(sit.caze, AUCUN_DRAPEAU);
	}
}

/// Fonction appelée à la fin de la partie. (ne fait rien, aucun bilan à afficher)
void partie_fin(){}
