#include "Player.hh"

using namespace std;

#define PLAYER_NAME Felix0

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

  virtual void play() {
    for (int cid = begin(me()); cid < end(me()); ++cid) {
      Car c = car(cid);
      control_car(c);
    }
  }

  void control_car(Car c) {
    if (!c.alive) return;

    // compute shortest path to every cell
    vector<vector<int> > dist;
    vector<vector<Dir> > ldir;
    Pos p0 = normalize(c.pos);
    bfs(p0, dist, ldir);

    // find nearest point bonus
    int mn_dist = -1;
    Pos goal;
    for (int y = 0; y < int(dist.size()); ++y) {
      for (int x = 0; x < int(dist[y].size()); ++x) {
        if (dist[y][x] == -1) continue;

        Pos cur = {y, x};
        CType type = cell(cur).type;
        if (type != WATER_BONUS) continue;

        if (dist[y][x] < mn_dist || mn_dist == -1) {
          mn_dist = dist[y][x];
          goal = cur;
        }
      }
    }

    // do nothing if no point bonus can be reached
    if (mn_dist == -1) return;

    // get first step in the path
    Dir dir;
    for (Pos p = goal; p != p0;) {
      int y = first(p);
      int x = second(p);
      dir = ldir[y][x];
      p = normalize(p - dir);
    }

    move(c.cid, dir);
  }

  void bfs(Pos p, vector<vector<int> >& dist, vector<vector<Dir> >& ldir) {
    int h = number_rows();
    int w = number_universe_columns();
    dist = vector<vector<int> >(h, vector<int>(w, -1));
    ldir = vector<vector<Dir> >(h, vector<Dir>(w));
    queue<Pos> q;

    int y0 = first(p);
    int x0 = second(p);
    dist[y0][x0] = 0;
    q.push(p);
    while (!q.empty()) {
      Pos p = q.front();
      q.pop();

      int y = first(p);
      int x = second(p);
      vector<Dir> dirs = all_directions();
      for (Dir dir : dirs) {
        int dy = first(dir);
        int dx = second(dir);
        Pos np = normalize({y + dy, x + dx});
        if (!within_universe(np)) continue;

        int ny = first(np);
        int nx = second(np);
        if (!within_window(np, round() + dist[y][x] + 1)) continue;

        if (dist[ny][nx] != -1) continue;

        if (!is_safe_move(p, dir)) continue;

        dist[ny][nx] = dist[y][x] + 1;
        ldir[ny][nx] = dir;
        q.push(np);
      }
    }
  }

  bool is_safe_move(Pos p, Dir dir) {
    int y0 = min(first(p), first(p + dir));
    int y1 = max(first(p), first(p + dir));
    int x0 = min(second(p), second(p + dir));
    int x1 = max(second(p), second(p + dir));
    for (int y = y0; y <= y1; ++y) {
      for (int x = x0; x <= x1; ++x) {
        Pos cur = normalize({y, x});
        if (cur == p) continue;

        CType type = cell(cur).type;
        if (type != EMPTY && type != WATER_BONUS && type != MISSILE_BONUS) {
          return false;
        }
      }
    }

    return true;
  }

  vector<Dir> all_directions() {
    vector<Dir> dirs;
    for (int dy = -1; dy <= 1; ++dy) {
      for (int dx = 0; dx <= 2; ++dx) {
        dirs.emplace_back(Dir{dy, dx});
      }
    }
    return dirs;
  }

  Pos normalize(Pos p) {
    int y = first(p);
    int x = second(p);
    int w = number_universe_columns();
    return {y, ((x % w) + w) % w};
  }
};

RegisterPlayer(PLAYER_NAME);

