#ifndef UTILS_H
#define UTILS_H

#include <bits/stdc++.h>
#include "prologin.hh"

const int INF = 1e9;

position DIRS[4] = {{-1,0},{1,0},{0,-1},{0,1}};

position operator+(position& a, position& b)
{
    return position { a.ligne + b.ligne, a.colonne + b.colonne };
}


struct dijk_sit
{
    position pos;
    bool accr;
    bool retour;
    int bonus, dist_pm, dist_pa, dist_tours;
    double score;

    void maj()
    {
        dist_tours = (dist_pa + NB_POINTS_ACTION-1)/ NB_POINTS_ACTION;
        dist_tours = std::max(dist_tours, (dist_pm + NB_POINTS_DEPLACEMENT-1) / NB_POINTS_DEPLACEMENT);

        score = ((double) bonus) / (3 * dist_tours + dist_pa + dist_pm + 1);
        score *= -1;
        score += 10;
    }

    inline int hash()
    {
        return ((pos.ligne * TAILLE_MINE) + pos.colonne) ;
    }
};

bool operator<(const dijk_sit& a, const dijk_sit& b) { return a.score > b.score; }


int dijk_dist[TAILLE_MINE][TAILLE_MINE][2];
std::pair<dijk_sit, action_hist> dijk_pere[TAILLE_MINE][TAILLE_MINE][2];

std::priority_queue<dijk_sit> q;


void dijk_valide(dijk_sit sit, dijk_sit pere, action_hist act)
{
    sit.maj();

    if(sit.pos.ligne < 0 || TAILLE_MINE <= sit.pos.ligne || sit.pos.colonne < 0 || TAILLE_MINE <= sit.pos.colonne)
        return;

    if(type_case(sit.pos) == OBSIDIENNE)
        return;
    
    if(sit.pos == position_taverne(adversaire()))
        return;

    act.sens = BAS;
    if(type_case(sit.pos) == GRANITE)
    {
        act.sens = HAUT;
        minerai minfo = info_minerai(sit.pos);
        if(minfo.resistance != -1)
            sit.dist_pa += COUT_MINER * minfo.resistance, sit.bonus += std::min(minfo.rendement,BUTIN_MAX);
        else
            sit.dist_pa += COUT_MINER;
    }

    if(nain_sur_case(sit.pos) == adversaire())
    {
        act.sens = HAUT;
        for(int i = 0; i < NB_NAINS; i++)
            if(info_nain(adversaire(), i).pos == sit.pos)
            {
                sit.dist_pa += (info_nain(adversaire(), i).vie + DEGAT_PIOCHE-1) / DEGAT_PIOCHE;
                sit.bonus += info_nain(adversaire(), i).butin;
                sit.bonus = std::min(sit.bonus, BUTIN_MAX);
            }
    }

    bool ok = sit.accr;
    if(!sit.accr)
    {
        for(int i = 0; i < 4 && !ok; i++)
        {
            sit.pos = sit.pos + DIRS[BAS];
            if(type_case(sit.pos) != LIBRE || nain_sur_case(sit.pos) == adversaire())
                ok = true;
        }
        sit.pos = sit.pos + DIRS[HAUT];
    }

    int* dans_dist = &dijk_dist[sit.pos.ligne][sit.pos.colonne][sit.accr];

    if(sit.dist_tours < *dans_dist)
    {
        if(ok)
        {
            *dans_dist = sit.dist_tours;
            dijk_pere[sit.pos.ligne][sit.pos.colonne][sit.accr] = std::make_pair(pere, act);
            // printf("pushing    pos %d %d   S %.3lf\n", sit.pos.ligne, sit.pos.colonne, sit.score);
            q.push(sit);
        }
    }
}


std::vector<action_hist> dijkstra(dijk_sit source, dijk_sit dest)
{
    for(int x = 0; x < TAILLE_MINE; x++)
        for(int y = 0; y < TAILLE_MINE; y++)
            for(int i = 0; i < 2; i++)
                dijk_dist[x][y][i] = INF, dijk_pere[x][y][i].first.dist_tours = -1;

    dijk_dist[source.pos.ligne][source.pos.colonne][source.accr] = 0;
    dijk_pere[source.pos.ligne][source.pos.colonne][source.accr].first.dist_tours = -1;

    while(!q.empty())
        q.pop();
    q.push(source);

    while(!q.empty())
    {
        dijk_sit curr = q.top();
        q.pop();

        if(dijk_dist[curr.pos.ligne][curr.pos.colonne][curr.accr] < curr.dist_tours)
            continue;

        dijk_sit nouv;
        action_hist act;

        if(!curr.retour)
        {
            
        }

        if(curr.accr)
        {
            act.atype = ACTION_LACHER;
            nouv = curr;
            nouv.accr = false;
            dijk_valide(nouv, curr, act);

            act.atype = ACTION_DEPLACER;
            nouv = curr;

            for(int i = 0; i < 4; i++)
            {
                act.dir = (direction) i;
                nouv.pos = curr.pos + DIRS[i];
                nouv.dist_pa = curr.dist_pa;
                nouv.dist_pm = curr.dist_pm;
                if(corde_sur_case(nouv.pos)) nouv.dist_pm += COUT_ESCALADER_CORDE;
                else                         nouv.dist_pm += COUT_ESCALADER;
                dijk_valide(nouv, curr, act);
            }
        }
        else
        {
            act.atype = ACTION_AGRIPPER;
            nouv = curr;
            nouv.accr = true;
            dijk_valide(nouv, curr, act);

            act.atype = ACTION_DEPLACER;
            nouv = curr;
            nouv.dist_pm += COUT_DEPLACEMENT;

            act.dir = DROITE;
            nouv.pos = curr.pos + DIRS[DROITE];
            dijk_valide(nouv, curr, act);

            act.dir = GAUCHE;
            nouv.pos = curr.pos + DIRS[GAUCHE];
            dijk_valide(nouv, curr, act);
        }
    }

    std::vector<action_hist> acts;

    std::stack<action_hist> st;
    auto curr = dijk_pere[dest.pos.ligne][dest.pos.colonne][dest.accr];
    while(curr.first.dist_tours != -1)
    {
        dijk_sit& sit = curr.first;
        debug_afficher_drapeau(sit.pos, DRAPEAU_BLEU);

        st.push(curr.second);

        if(curr.second.sens == HAUT)
        {
            action_hist a2 = curr.second;
            a2.atype = ACTION_MINER;
            st.push(a2);
        }

        curr = dijk_pere[sit.pos.ligne][sit.pos.colonne][sit.accr];
    }

    while(!st.empty())
    {
        acts.push_back(st.top());
        st.pop();
    }

    return acts;
}

#endif
