#include "aoc.h"

namespace aoc2022 {

struct pos {
  int x;
  int y;

  bool operator==(pos p) const noexcept {
    return x == p.x && y == p.y;
  }
};

bool is_valid(pos p, const std::map<blizzard, int>&m, valley& v) {
  auto b = p.x >= 0 && p.x < v.width && p.y >= 0 && p.y < v.height;
  return b && m.find(blizzard{p.x, p.y, '.'}) == m.end() && v.get(p.y, p.x) == '.';
}

void expedition(int m, pos p, pos target, valley& v, int* min, bool pass) {
  if (*min < INT32_MAX && m > *min) return;
  if (p == target) {
    printf("arrived by %d !!!\n", m);
    if (*min > m) *min = m;
  }
  else {
    auto& t = v.get_time(p.y, p.x);

    if (m < t || pass) {
      // printf("(%d, %d) in %d, was %d\n", p.x, p.y, m, t);
      if (!pass) t = m;

      v.next();
      std::map<blizzard, int> mp; 
      for (auto& b: v.blz) {
        auto p = mp.insert({b, 1});
        if (!p.second) {
          p.first->second += 1;
        }
      }

      pos mv0[5] = {
        {p.x, p.y+1},
        {p.x+1, p.y},
        {p.x, p.y-1},
        {p.x-1, p.y},
        p,
      };
      for (int i = 0; i < 5; i++) {
        auto mv = mv0[i];
        if (is_valid(mv, mp, v)) {
          auto blz = v.blz;
          expedition(m + 1, mv, target, v, min, i > 2);
          v.blz = blz;
        }
      }
    }
  }
}

std::pair<int, int> day24(line_view file) {
  // valley v{8,6}; //sample
  valley v{152,22};

  int height{0};
  per_line(file, [&v, &height](line_view lv) {
    v.load(height++, lv);
    return true;
  });

  int min{INT32_MAX};
  // v.print();
  expedition(0, {1, 0}, {150, 21}, v, &min, false);

  return {min, 0};
}
}