/**
 * 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 et qui décroît en fonction du
 *   nombre de tours à attendre avant que l'alien n'arrive
 * - ce score favorise aussi (voire +) les cases qui permettent 
 *   d'éjecter immédiatement un joueur
 * - choix de la case au score le plus élevé, déplacement tant que
 *   possible
 * - pousser quelqu'un si possible sans attendre le prochain tour
 */



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



/// Fonctions/variables/structures/constantes utilitaires
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
vector<vector<alien_info > > aliens(TAILLE_BANQUISE, vector<alien_info > (TAILLE_BANQUISE, {{-1,-1},-1,-1,-1,-1}));

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) {}
	
	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;
				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;
			if(paS >= NB_POINTS_ACTION) {
				nbToursS ++;
				paS %= NB_POINTS_ACTION;
			}
			ret.push_back(Situation(posFin, caze, nbToursS, paS));
		}
		return ret;
	}
};

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 une 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;
	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)
				file.push(suivant);
	}
	return {ret, visite};
}

/// Retrouve le chemin menant à une case depuis l'agent. front() = arrivée, back() = départ
vector<Situation> cheminVers(ResultatsRecherche resultats, int ou) { // le chemin est a l'envers !
	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
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) {
		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 {
		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);
	}
	/// ne devrait jamais arriver
	printf("WTF depl\n");
	return DIRECTION_INVALIDE;
}

/// Cherche quelqu'un à pousser
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))
					return make_pair(true, DEPLACEMENTS[iDir].direct);
			}
		}
	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)
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 nb 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 à la case en cours de capture (pour éviter de l'arrêter).
 * Attribue environ 90 000 aux cases contenant dans le présent ou le 
 * futur un alien capturable avant qu'il ne parte; score décroissant
 * en fonction de l'attente.
 * Attribue environ 90 000 aux cases atteignables en un seul tour et
 * qui permettent d'éjecter un manchot adverse d'un alien immédiatement
 * après. Avantage aux aliens les plus rapporteurs en points.
 * Dans les autres cas, attribue 0.
 */
int scoreCase(int iPos, int iAgent, ResultatsRecherche resultats) {
	position caze = resultats.positions[iPos].caze;
	/// Case en cours de capture
	if(caze == position_agent(moi(),iAgent) && alien_sur_case(caze))
		return 10000000;
		
	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];
	
	/// Case contenant un alien maintenant ou dans le futur
	if(alien.tour_invasion >= 0) {
		int dernierTourAlien = alien.tour_invasion+alien.duree_invasion-1;
		int attente = max(0, alien.tour_invasion-tourArrivee);
		/// S'il est capturable avant qu'il ne parte
		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;
		}
	}
	
	/// Cases permettant d'éjecter lors du tour actuel un manchot adverse
	if(tourArrivee == tour_actuel() && paRestant >= COUT_POUSSER) {
		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+(int)((double)alien.points_capture/maxPoints*10)+paRestant;
		}
	}
	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;
			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 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
			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é !
		ejecterDanger(iAgent);
		
		/// Détermination meilleure case (score maximal)
		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;
			}
		}
		
		/// Chemin vers la meilleure case
		vector<Situation> chemin = cheminVers(resultats, iCorres);
		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
		pair<bool,direction> pousse = dirPousser(position_agent(moi(), iAgent));
		if(pousse.first)
			pousser(iAgent, pousse.second);
		
		for(Situation sit : chemin)
			debug_afficher_drapeau(sit.caze, AUCUN_DRAPEAU);
	}
}

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