#include "common.h"
#include <vector>
#include <deque>

namespace aoc2022 {

struct heightmap {
  static const int row = 41;
  static const int col = 66;

  struct pos {
    int x;
    int y;

    friend bool operator==(pos p1, pos p2) {
      return p1.x == p2.x && p1.y == p2.y;
    }
  };

  struct height {
    char h;
    int  v = INT32_MAX;
  };

  height heights[row * col];
  pos start;
  pos end;

  char& get(pos p) {
    return heights[p.y * col + p.x].h;
  }

  int& was(pos p) {
    return heights[p.y * col + p.x].v;
  }

  bool valid(pos p) {
    return p.x >= 0 && p.x < col && p.y >= 0 && p.y < row;
  }

  void get_next(pos p, pos next[], int* n) {
    pos ps[] = {
      {p.x, p.y - 1}, // UP
      {p.x, p.y + 1}, // DOWN
      {p.x - 1, p.y}, // LEFT
      {p.x + 1, p.y}, // RIGHT
    };
    for (int i = 0; i < 4; i++) {
      if (valid(ps[i])) {
        bool b1 = get(ps[i]) == get(p) + 1;
        bool b2 = get(ps[i]) <= get(p);
        if (b1 || b2) {
          next[*n] = ps[i];
          *n += 1;
        }
      }
    }
  }

  void get_prev(pos p, pos prev[], int* n) {
    pos ps[] = {
      {p.x, p.y - 1}, // UP
      {p.x, p.y + 1}, // DOWN
      {p.x - 1, p.y}, // LEFT
      {p.x + 1, p.y}, // RIGHT
    };
    for (int i = 0; i < 4; i++) {
      if (valid(ps[i])) {
        bool b1 = get(ps[i]) == get(p) - 1;
        bool b2 = get(ps[i]) >= get(p);
        if (b1 || b2) {
          prev[*n] = ps[i];
          *n += 1;
        }
      }
    }
  }

  void flood(pos p) {
    was(p) = 0;
    std::deque<pos> q = {p};
    while (!q.empty()) {
      pos px = q.front();
      q.pop_front();
      pos next[4];
      int n{0};
      get_next(px, next, &n);
      for (int i = 0; i < n; i++){
        int x = was(px) + 1;
        if (x < was(next[i])) {
            was(next[i]) = x;
            q.push_back(next[i]);
        }
      }
    }
  }

  void flood_down(pos p, int* nearest) {
    was(p) = 0;
    std::deque<pos> q = {p};
    while (!q.empty()) {
      pos px = q.front();
      q.pop_front();
      if (get(px) == 'a') {
        *nearest = was(px);
        return;
      }
      pos prev[4];
      int n{0};
      get_prev(px, prev, &n);
      for (int i = 0; i < n; i++) {
        int x = was(px) + 1;
        if (x < was(prev[i])) {
            was(prev[i]) = x;
            q.push_back(prev[i]);
        }
      }
    }
  }

  void reset() {
    for (int i = 0; i < row; i++) {
      for (int j = 0; j < col; j++) {
        was({j, i}) = INT32_MAX;
      }
    }
  }

  void print() {
    for (int i = 0; i < row; i++) {
      for (int j = 0; j < col; j++) {
        printf("%c", get({j, i}));
      }
      printf("\n");
    }
  }

  void load(int r, line_view lv) {
    const char* p = lv.line;
    for (int c = 0; c < col; c++) {
      get({c, r}) = *(p + c); 
      if (*(p + c) == 'S') {
        start = pos{c, r};
        get({c, r}) = 'a';
      }
      if (*(p + c) == 'E') {
        end = pos{c, r};
        get({c, r}) = 'z';
      }
    }
  }
};

std::pair<int, int> day12(line_view);
}