#include "Player.hh"
#include <string.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;


#define PLAYER_NAME Lobo


/**
 * Dumb-ass Tron player
 */
struct PLAYER_NAME:public Player
{

    // typedefs
    typedef vector < int >IntVec;
    typedef queue < Vertex > VtxQue;
    typedef queue < int >IntQue;


    // Variables
    int nhogs;
    IntVec hogs;


    // initialize stuff
    void init ()
    {
        hogs = bikes (me ());
        nhogs = hogs.size ();
    }

    int closest_non_wall (const Vertex & vert)
    {
        const int vert_id = vert.id;
        bool avail[nb_vertices ()];
        memset (avail, true, sizeof (avail));
        avail[vert_id] = false;
        int par[nb_vertices ()];
        par[vert_id] = vert_id;
        IntQue que;
        que.push (vert_id);
        while (!que.empty ()) {
            const int que_vert_id = que.front ();
            const Vertex & que_vert = vertex (que_vert_id);
            const IntVec & adj = que_vert.neighbours;
            const int asiz = adj.size ();
            for (int i = 0; i < asiz; ++i) {
                const int adj_vert_id = adj[i];
                if (avail[adj_vert_id]) {
                    avail[adj_vert_id] = false;
                    par[adj_vert_id] = que_vert_id;
                    const Vertex & adj_vert = vertex (adj_vert_id);
                    if (adj_vert.wall == -1) {
                        int nvert = adj_vert_id;
                        while (par[nvert] != vert_id) {
                            nvert = par[nvert];
                        }
                        return nvert;
                    }
                    else {
                        que.push (adj_vert_id);
                    }
                }
            }
            que.pop ();
        }
        const IntVec & adj = vert.neighbours;
        const int asiz = adj.size ();
        return adj[rand () % asiz];
    }

    // choose the vertex that can take us the farthest
    void move_hog (const Bike & hog, int &nvert, bool & cheat)
    {
        // root vertices
        const int vert_id = hog.vertex;
        const Vertex & hog_vertex = vertex (vert_id);
        // parents' ids
        int par[nb_vertices ()];
        par[vert_id] = vert_id;
        // distances
        int dis[nb_vertices ()];
        memset (dis, -1, sizeof (dis));
        // mark cells with close bikes as unwelcome
        const int total_bikes = nb_bikes () * nb_players ();
        for (int i = 0; i < total_bikes; ++i) {
            if (hog.id != i) {
                const Bike & ohog = bike (i);
                if (ohog.alive) {
                    const Vertex & vert = vertex (ohog.vertex);
                    const IntVec & adj = vert.neighbours;
                    const int asiz = adj.size ();
                    for (int j = 0; j < asiz; ++j) {
                        dis[adj[j]] = -2;
                    }
                }
            }
        }
        dis[vert_id] = 0;
        // bfs queue
        VtxQue que;
        que.push (hog_vertex);
        while (!que.empty ()) {
            const Vertex & vert = que.front ();
            const int vid = vert.id;
            const int vdis = dis[vid];
            // randomize directions
            IntVec adj = vert.neighbours;
            random_shuffle (adj.begin (), adj.end ());
            const int asiz = adj.size ();
            for (int i = 0; i < asiz; ++i) {
                const int adj_vert_id = adj[i];
                const Vertex & adj_vert = vertex (adj_vert_id);
                if (adj_vert.wall == -1 && dis[adj_vert_id] == -1) {
                    // bonus vertices add extra weigh (distance)
                    // so the bike will be attracted to that vertex,
                    // and sometimes even pick it up! :)
                    int weigh = 1;
                    if (adj_vert.bonus != None) {
                        weigh = 8;
                    }
                    dis[adj_vert_id] = vdis + weigh;
                    par[adj_vert_id] = vid;
                    que.push (adj_vert);
                }
            }
            que.pop ();
        }
        // find farthest
        int farthest = -1;
        int max_dis = 0;
        for (int i = 0; i < nb_vertices (); ++i) {
            if (max_dis < dis[i]) {
                max_dis = dis[i];
                farthest = i;
            }
        }
        // pick next vertex
        if (farthest == -1) {
            // maybe path is risky but make the most of it
            bool search = true;
            const IntVec & adj = hog_vertex.neighbours;
            const int asiz = adj.size ();
            for (int i = 0; search && i < asiz; ++i) {
                const int adj_vert_id = adj[i];
                const Vertex & adj_vert = vertex (adj_vert_id);
                if (adj_vert.wall == -1) {
                    nvert = adj_vert_id;
                    search = false;
                }
            }
            if (search) {
                // we really got trapped and we gonna die -pick a random direction
                nvert = closest_non_wall (hog_vertex);
                // use ghost if we're gonna crash -this can save our life
                if (hog.bonus == Ghost) {
                    cheat = true;
                }
            }
        }
        else {
            nvert = farthest;
            while (par[nvert] != vert_id) {
                nvert = par[nvert];
            }
            // cerr << "move from " << vert_id << " to " << nvert << ", farthest node " << farthest << ", " << max_dis << " away" << endl;
        }
        // use turbo as soon as we have it
        if (hog.bonus == Turbo) {
            cheat = true;
        }
    }

    // move all my bikes
    void move_hogs ()
    {
        for (int i = 0; i < nhogs; ++i) {
            const Bike & hog = bike (hogs[i]);
            // make sure the hog can move
            if (hog.alive && (!(round () % 2) || hog.turbo_duration > 0)) {
                // Now we just need need to find destination vertex & whether to use bonus
                int nvert = -1;
                bool cheat = false;
                move_hog (hog, nvert, cheat);
                // do move
                const Movement move (hog.id, nvert, cheat);
                command (move);
            }
        }
    }

    void play ()
    {
        if (!round ()) {
            init ();
        }
        move_hogs ();
    }


    static Player *factory ()
    {
        return new PLAYER_NAME;
    }

};

RegisterPlayer (PLAYER_NAME);
