#include "Player.hh"
#include <climits>
#include <cfloat>
#include <queue>
#include <iterator>

/**
 * Write the name of your player and save this file
 * with the same name and .cc extension.
 */
#define PLAYER_NAME Smart


struct PLAYER_NAME : public Player {

  /**
   * Factory: returns a new instance of this class.
   * Do not modify this function.
   */
  static Player* factory () {
    return new PLAYER_NAME;
  }

  /**
   * Types and attributes for your player can be defined here.
   */

  static constexpr Dir dirs[] = { Down, Right, Up, Left };

  static constexpr NutrientType nutrients[] = { Carbohydrate, Protein, Lipid };

  static constexpr BonusType bonuses[] = {Bread, Seed, Leaf};
  
  static constexpr int oo = INT_MAX;

  const int MIN_DIST_BONUS = 5; // But ignore bonuses too close to the queen.
  
  set<int> panick;
  vector< vector<int> > free;

  const vector< vector<int> >* pqdist;
  map<int, int> goal;

  class Soldier_validator {

    PLAYER_NAME& obj;
    bool sacrifice;

  public:

    Soldier_validator(PLAYER_NAME& obj, bool sacrifice) :
      obj(obj), sacrifice(sacrifice) { }

    bool valid(Pos p) { return obj.valid_for_soldier(p, sacrifice); }
  };


  bool valid_for_soldier(Pos p, bool sacrifice) {
    if (not pos_ok(p))  return false;
    const Cell& c = cell(p);
    if (c.type == Water) return false;
    if (c.id == -1)      return true;
    Ant a = ant(c.id);
    if (ant(c.id).player == me())                    return false;
    if (ant(c.id).type == Queen)                     return false;
    if (ant(c.id).type == Soldier and not sacrifice) return false;

    return true;
  }


  class Worker_validator {

    PLAYER_NAME& obj;
    bool sacrifice;

  public:

    Worker_validator(PLAYER_NAME& obj, bool sacrifice) :
      obj(obj), sacrifice(sacrifice) { }

    bool valid(Pos p) { return obj.valid_for_worker(p, sacrifice); }
  };


  bool valid_for_worker(Pos p, bool sacrifice) {
    if (not pos_ok(p))   return false;
    const Cell& c = cell(p);
    if (c.type == Water) return false;
    if (c.id == -1)      return true;
    Ant a = ant(c.id);
    if (ant(c.id).player == me())                   return false;
    if (ant(c.id).type != Worker)                   return false;
    if (ant(c.id).type == Worker and not sacrifice) return false;

    return true;
  }


  class Queen_validator {

    PLAYER_NAME& obj;
    bool sacrifice;

  public:

    Queen_validator(PLAYER_NAME& obj, bool sacrifice) :
      obj(obj), sacrifice(sacrifice) { }

    bool valid(Pos p) { return obj.valid_for_queen(p, sacrifice); }
  };


  bool valid_for_queen(Pos p, bool sacrifice) {
    if (not pos_ok(p))   return false;
    const Cell& c = cell(p);
    if (c.type == Water) return false;
    if (c.id == -1)      return true;
    Ant a = ant(c.id);
    // if (ant(c.id).player == me()) return false;
    if (ant(c.id).type == Queen and not sacrifice) return false;

    return true;
  }


  template <typename Validator>
  struct Distance_matrix {

    int r, c;
    Pos ini;
    vector< vector<int> > dist;
    vector< vector<Pos> > prnt;

  public:

    Distance_matrix(int r, int c, Pos ini, Validator v) :
      r(r),
      c(c),
      ini(ini),
      dist(vector< vector<int> >(r, vector<int>(c, +oo))),
      prnt(vector< vector<Pos> >(r, vector<Pos>(c, Pos(-1,-1)))) {

      queue<Pos> q;

      dist[ini.i][ini.j] = 0;
      q.push(ini);

      while (not q.empty()) {
        Pos p = q.front();
        q.pop();
        for (Dir d : dirs) {
          Pos n = p + d;
          if (v.valid(n) and dist[n.i][n.j] == +oo) {
            dist[n.i][n.j] = 1 + dist[p.i][p.j];
            prnt[n.i][n.j] = p;
            q.push(n);
          }
        }
      }
    }


    int distance(Pos p) const { return dist[p.i][p.j]; }


    Dir direction(Pos fin) const {

      _my_assert(ini != fin, "origin should be different from destination");
      _my_assert(dist[ini.i][ini.j] == 0,   "problem with distance of origin");
      _my_assert(dist[fin.i][fin.j] != +oo, "problem with distance of destination");

      Pos p = fin;
      _my_assert(0 <= p.i and p.i < r and 0 <= p.j and p.j < c, "position should be ok [initialization]");

      while (ini != prnt[p.i][p.j]) {
        p = prnt[p.i][p.j];
        _my_assert(0 <= p.i and p.i < r and 0 <= p.j and p.j < c, "position should be ok [loop]");
      }

      for (Dir d : dirs)
        if (ini + d == p) return d;

      _my_assert(false, "reached unreachable code");
      return Down;
    }


    vector<Dir> best_directions(const vector<Pos>& vp, const vector< vector<int> >& free) const {
      set<Dir> sbdir;
      int bdst = +oo;
      for (Pos p : vp) {
        int dst = distance(p);
        if (dst < +oo and dst <= bdst) {
          Dir dir = direction(p);
          Pos q = ini + dir;
          if (free[q.i][q.j]) {
            if (dst < bdst) {
              sbdir = {dir};
              bdst = dst;
            }
            else sbdir.insert(dir);
          }
        }
      }
      return vector<Dir>(sbdir.begin(), sbdir.end());
    }

  };


  bool try_move_to_one_direction_in(const Ant& a, const vector<Dir>& bdirs) {
    if (bdirs.empty()) return false;
    Dir bdir = bdirs[random(0, bdirs.size()-1)];
    Pos p = a.pos + bdir;
    free[p.i][p.j] = false;
    move(a.id, bdir);
    return true;
  }


  bool soldier_try_go_to_closest_enemy_worker(const Ant& s, const Distance_matrix<Soldier_validator>& dm) {

    vector<Pos> cands;

      for (int pl = 0; pl < num_players(); ++pl)
        if (pl != me())
          for (int wid : workers(pl))
            cands.push_back(ant(wid).pos);
    
    return try_move_to_one_direction_in(s, dm.best_directions(cands, free));
  }


  bool soldier_try_go_to_closest_enemy_soldier(const Ant& s, const Distance_matrix<Soldier_validator>& dm) {

    vector<Pos> cands;
    for (int pl = 0; pl < num_players(); ++pl)
      if (pl != me())
        for (int sid : soldiers(pl))
          cands.push_back(ant(sid).pos);

    return try_move_to_one_direction_in(s, dm.best_directions(cands, free));
  }
  

  bool there_is_worker_in_panick_around(const Ant& s) {
    Pos sp = s.pos;
    for (Dir d : dirs) {
      Pos p = sp + d;
      if (pos_ok(p)) {
        Cell c = cell(p);
        if (c.id != -1) {
          Ant a = ant(c.id);
          if (a.player == me() and a.type == Worker and panick.count(a.id)) {
            return true;
          }
        }
      }
    }
    return false;
  }


  void play_soldier(int sid) {
    Ant s = ant(sid);

    if (flee_from_close_enemies(s, false)) return;
    
    Distance_matrix<Soldier_validator> dm(board_rows(), board_cols(), s.pos, Soldier_validator(*this, false));

    if (there_is_worker_in_panick_around(s)) {
      Distance_matrix<Soldier_validator> dm2(board_rows(), board_cols(), s.pos, Soldier_validator(*this, true));
      if (soldier_try_go_to_closest_enemy_soldier(s, dm2)) return;
    }
    else {
      if (soldier_try_go_to_closest_enemy_worker(s, dm)) return;
    }
  }


  bool worker_try_go_to_closest_bonus(const Ant& w, const Distance_matrix<Worker_validator>& dm) {

    const vector< vector<int> >& qdist = *pqdist;

    Pos wp = w.pos;

    if (cell(wp).bonus != None and qdist[wp.i][wp.j] >= MIN_DIST_BONUS) {
      take(w.id);
      return true;
    }
    vector<Pos> cands;
    for (int i = 0; i < board_rows(); ++i)
      for (int j = 0; j < board_cols(); ++j) {
        Cell c = cell(i, j);
        if (c.bonus != None and c.id == -1 and qdist[i][j] >= MIN_DIST_BONUS)
          cands.push_back(Pos(i, j));
      }

    return try_move_to_one_direction_in(w, dm.best_directions(cands, free));
  }


  set<Pos> empty_cells_close_to_queen(const Ant& w, const Distance_matrix<Worker_validator>& dm) {
    const vector< vector<int> >& qdist = *pqdist;

    vector<Pos> cands;
    int bdst = +oo;
    for (int i = 0; i < board_rows(); ++i)
      for (int j = 0; j < board_cols(); ++j) {
        Pos p(i, j);
        Cell c = cell(p);
        if (c.bonus == None and (p == w.pos or valid_for_worker(p, false))) {
          if      (qdist[i][j] <  bdst) {
            cands = {p};
            bdst = qdist[i][j];
          }
          else if (qdist[i][j] < +oo and qdist[i][j] == bdst) {
            cands.push_back(p);
          }
        }
      }

    set<Pos> sbpos;
    bdst = +oo;
    for (Pos pos : cands) {
      int dst = dm.distance(pos);
      if (dst < bdst) {
        sbpos = {pos};
        bdst = dst;
      }
      else if (dst < +oo and dst == bdst)
        sbpos.insert(pos);
    }
    return sbpos;
  }


  bool worker_try_leave_bonus_close_to_queen(const Ant& w, const Distance_matrix<Worker_validator>& dm) {

    const vector< vector<int> >& qdist = *pqdist;
    
    set<Pos> sbpos = empty_cells_close_to_queen(w, dm);

    if (not sbpos.empty()) {

      if ((sbpos.size() == 1 and *sbpos.begin() == w.pos) or
          (qdist[w.pos.i][w.pos.j] < MIN_DIST_BONUS)) {
        leave(w.id);
        return true;
      }

      for (Pos bpos : sbpos) {
        Dir d = dm.direction(bpos);
        Pos p = w.pos + d;
        if (free[p.i][p.j]) {
          free[p.i][p.j] = false;
          move(w.id, d);
          return true;
        }
      }
    }
    return false;
  }


  double danger_around(Pos ini, int dmax, bool worker) {

    int r = board_rows();
    int c = board_cols();

    double dan = 0;
    vector< vector<int> > dist(r, vector<int>(c, +oo));
    queue<Pos> q;

    dist[ini.i][ini.j] = 0;
    q.push(ini);

    while (not q.empty()) {
      Pos p = q.front();
      q.pop();
      if (dist[p.i][p.j] >= dmax) return dan;
      for (Dir d : dirs) {
        Pos n = p + d;
        if (pos_ok(n) and dist[n.i][n.j] == +oo) {
          Cell c = cell(n);
          if (c.type != Water) {
            if (c.id != -1 and ant(c.id).player != me()) {
              if (worker or ant(c.id).type == Queen) {
                dan += pow(10, -dist[p.i][p.j]);
              }
            }
            dist[n.i][n.j] = 1 + dist[p.i][p.j];
            q.push(n);
          }
        }
      }
    }
    return dan;
  }


  bool flee_from_close_enemies(const Ant& a, bool worker) {
    const double oo = DBL_MAX;
    const int DMAX = 2;
    bool danger = (danger_around(a.pos, DMAX, worker) > 0);
    vector<double> dir2dan(4, +oo);
    for (Dir d : dirs) {
      Pos p = a.pos + d;
      if (pos_ok(p) and free[p.i][p.j]) {
        Cell c = cell(p);
        bool go;
        if (worker) go = (c.type == Soil and c.id == -1);
        else        go = (c.type == Soil and (c.id == -1 or (ant(c.id).player != me()and ant(c.id).type == Soldier) ) );
        if (go) {
          dir2dan[d] = danger_around(p, DMAX, worker);
          if (dir2dan[d] > 0)
            danger = true;
        }
      }
    }
    if (not danger) return false;

    panick.insert(a.id);
    
    auto min = *min_element(dir2dan.begin(), dir2dan.end());
    if (min == +oo) return false; // Cannot move

    // cerr << endl;
    // for (auto x : dir2dan) {
    //   cerr << x << ' ';
    // }
    // cerr << endl;
    
    for (Dir d : dirs) {
      if (dir2dan[d] == min) {
        Pos p = a.pos + d;
        free[p.i][p.j] = false;
        // cerr << "Ant " << a.id << " flees following direction " << d << endl;
        move(a.id, d);
        return true;
      }
    }
    return false;
  }


  void play_worker(int wid) {
    Ant w = ant(wid);

    if (flee_from_close_enemies(w, true)) return;

    Distance_matrix<Worker_validator> dm(board_rows(), board_cols(), w.pos, Worker_validator(*this, false));
    if (w.bonus == None) {
      if (worker_try_go_to_closest_bonus(w, dm)) return;
    }
    else {
      if (worker_try_leave_bonus_close_to_queen(w, dm)) return;
    }
  }


  bool enough_for_egg(const Ant& q, AntType t) {
    for (auto n : nutrients)
      if (needed(t, n) > q.reserve[n])
        return false;
    return true;
  }


  bool queen_try_lay_egg(const Ant& q, AntType t) {
    Pos qp = q.pos;
    if (enough_for_egg(q, t))
      for (Dir d : dirs) {
        Pos r = qp + d;
        if (pos_ok(r)) {
          Cell rc = cell(r);
          if (rc.type != Water and rc.id == -1 and free[r.i][r.j]) {
            free[r.i][r.j] = false;
            lay(q.id, d, t);
            return true;
          }
        }
      }
    return false;
  }


  bool queen_try_go_to_closest_bonus(const Ant& q, Distance_matrix<Queen_validator>& dm, const set<BonusType>& goal) {

    vector<Pos> cands;
    for (int i = 0; i < board_rows(); ++i)
      for (int j = 0; j < board_cols(); ++j) {
        Pos p(i, j);
        if (p != q.pos
            and cell(p).bonus != None
            and goal.count(cell(p).bonus)
            and dm.distance(p) < +oo) {
          Dir d = dm.direction(p);
          Cell c = cell(q.pos + d);
          if (c.id == -1 or ant(c.id).player != me())
            cands.push_back(p);
        }
      }
    return try_move_to_one_direction_in(q, dm.best_directions(cands, free));
  }


  bool queen_try_go_to_closest_enemy_queen(const Ant& q, Distance_matrix<Queen_validator>& dm) {

    vector<Pos> cands;
    for (int pl = 0; pl < num_players(); ++pl)
      if (pl != me())
        for (int qid : queens(pl))
          cands.push_back(ant(qid).pos);

    return try_move_to_one_direction_in(q, dm.best_directions(cands, free));
  }


  bool queen_try_kill_neighbour_enemy(const Ant& q, bool only_soldiers) {
    Pos qp = q.pos;
    for (Dir d : dirs) {
      Pos p = qp + d;
      if (pos_ok(p) and free[p.i][p.j]) {
        Cell c = cell(p);
        if (c.id != -1) {
          Ant a = ant(c.id);
          if (a.player != me()
              and a.type != Queen
              and (not only_soldiers or a.type == Soldier)) {
            free[p.i][p.j] = false;
            move(q.id, d);
            return true;
          }
        }
      }
    }
    return false;
  }


  bool queen_try_go_to_neighbour_bonus(const Ant& q) {
    Pos qp = q.pos;
    for (Dir d : dirs) {
      Pos p = qp + d;
      if (pos_ok(p) and free[p.i][p.j]) {
        Cell c = cell(p);
        if (c.bonus != None and (c.id == -1 or ant(c.id).player != me())) {
          free[p.i][p.j] = false;
          move(q.id, d);
          return true;
        }
      }
    }
    return false;
  }


  void play_queen(const Ant& q, Distance_matrix<Queen_validator>& dm) {
    if (round() % queen_period() == 0) {
      if (queen_try_kill_neighbour_enemy(q,  true)) return;
      if (queen_try_kill_neighbour_enemy(q, false)) return;
    }
    int num_workers  =  workers(me()).size();
    int num_soldiers = soldiers(me()).size();
    if (queen_try_lay_egg(q, Soldier)) return;
    if (num_soldiers > num_workers/3 and queen_try_lay_egg(q, Worker)) return;
    if (round() % queen_period() == 0) {
      if (queen_try_go_to_neighbour_bonus(q)) return;

      set<BonusType> goal_bonuses;
      for (auto n : nutrients) {
        if (q.reserve[n] == 0)
          for (auto b : bonuses) {
            if (contains(b, n)) {
              goal_bonuses.insert(b);
            }
          }
      }
      if (goal_bonuses.empty()) goal_bonuses = {Bread, Seed, Leaf};
      
      if (queen_try_go_to_closest_bonus(q, dm, goal_bonuses)) return;
    }
  }


  virtual void play() {

    panick.clear();
    free = vector<vector<int>>(board_rows(), vector<int>(board_cols(), true));

    vector<int> vqids = queens(me());
    if (vqids.empty()) return;
    Ant q = ant(vqids[0]);
    Distance_matrix<Queen_validator> dm(board_rows(), board_cols(), q.pos, Queen_validator(*this, false));
    pqdist = &dm.dist;
    play_queen(q, dm);

    vector<int> vwids = workers(me());
    for (int wid : vwids)
      play_worker(wid);

    // cerr << "Workers in panick mode:";
    // for (int id : panick) {
    //   cerr << ' ' << id ;
    // }
    // cerr << endl;
    
    vector<int> vsids = soldiers(me());
    for (int sid : vsids)
      play_soldier(sid);

  }

};

constexpr          Dir PLAYER_NAME::dirs     [];
constexpr NutrientType PLAYER_NAME::nutrients[];
constexpr    BonusType PLAYER_NAME::bonuses  [];

/**
 * Do not modify the following line.
 */
RegisterPlayer(PLAYER_NAME);
