/* Problem  source: https://leetcode.com/problems/number-of-islands/
 */

#include <iostream>
#include <limits>
#include <stack>
#include <unordered_set>
#include <vector>

struct matrix_location {
  unsigned c; // column
  unsigned r; // row
  bool operator==(const matrix_location &other) const {
    return c == other.c && r == other.r;
  };
};

class matrix_location_hash {
private:
  unsigned n_cols;

public:
  matrix_location_hash(const unsigned num_of_cols, const unsigned num_of_rows)
      : n_cols(num_of_cols) {
    if (num_of_rows >
        std::numeric_limits<unsigned long long>::max() / num_of_cols)
      throw "Grid too big, cannot represent all cells with unique number for "
            "efficient hashing";
  };
  std::size_t operator()(const matrix_location &m) const {
    unsigned long long cell = m.c + m.r * n_cols;
    return std::hash<unsigned long long>()(cell);
  }
};

unsigned num_of_islands(const std::vector<std::vector<char>> &grid) {
  unsigned n_islands = 0;
  matrix_location_hash ml_hash(grid.size(),
                               grid[0].size()); // FIXME: potential seg fault
  std::unordered_set<matrix_location, matrix_location_hash> unexplored_land(
      10, ml_hash);
  for (unsigned i = 0, columns = grid.size(); i < columns; i++) {
    for (unsigned j = 0, rows = grid[i].size(); j < rows; j++) {
      if (grid[i][j] == '0') {
      } else if (grid[i][j] == '1') {
        unexplored_land.insert({i, j});
      } else {
        throw "Input grid cannot have elements other than '0' or '1'";
      }
    }
  }
  while (unexplored_land.size()) {
    for (auto &loc : unexplored_land) {
      std::stack<matrix_location> sub_explore({loc});
      bool island_added = false;
      while (!sub_explore.empty()) {
        matrix_location curr_loc = sub_explore.top();
        matrix_location above = {curr_loc.c - 1, curr_loc.r},
                        left = {curr_loc.c, curr_loc.r - 1},
                        right = {curr_loc.c, curr_loc.r + 1},
                        below = {curr_loc.c + 1, curr_loc.r};
        sub_explore.pop();
        if (!island_added) {
          n_islands++;
          island_added = true;
        }
        if (unexplored_land.count(above)) {
          sub_explore.push(above);
        }
        if (unexplored_land.count(left)) {
          sub_explore.push(left);
        }
        if (unexplored_land.count(right)) {
          sub_explore.push(right);
        }
        if (unexplored_land.count(below)) {
          sub_explore.push(below);
        }
        unexplored_land.erase(curr_loc);
      }
      break;
    }
  }
  return n_islands;
}

int main() {
  const std::vector<std::vector<char>> grid = {{'1', '1', '1', '1', '0'},
                                               {'1', '1', '0', '1', '0'},
                                               {'1', '1', '0', '0', '0'},
                                               {'0', '0', '0', '0', '0'}},
                                       grid2 = {{'1', '1', '0', '0', '0'},
                                                {'1', '1', '0', '0', '0'},
                                                {'0', '0', '1', '0', '0'},
                                                {'0', '0', '0', '1', '1'}};
  std::cout << num_of_islands(grid) << '\n' << num_of_islands(grid2) << "\n";
  return 0;
}