#ifndef UTILS_H
#define UTILS_H

#include <bits/stdc++.h>
#include "prologin.hh"
using namespace std;

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

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


struct dijk_sit { position pos; bool accr; int dist; };

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

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


inline void dijk_valide(priority_queue<dijk_sit>& q, dijk_sit& sit,
                        const dijk_sit& pere, const action_hist& act)
{
    int* dans_dist = &dijk_dist[sit.pos.ligne][sit.pos.colonne][sit.accr];

    if(sit.dist < *dans_dist)
    {
        *dans_dist = sit.dist;
        dijk_pere[sit.pos.ligne][sit.pos.colonne][sit.accr] = pere;
        q.push(sit);
    }
}


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] = 1000*1000*1000;

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

    std::priority_queue<dijk_sit> q;
    q.push(source);

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

        if(dijk_dist[curr.pos.ligne][curr.pos.colonne] <= curr.d)
            continue;

        dijk_sit nouv = curr;

        for(int i = 0; i < 4; i++)
        {
            nouv.pos = curr.pos + DIRS[i];
            dijk_valide(q, nouv, curr);
        }
    }
}

#endif
