aoc

My solutions for the Advent of Code
git clone https://git.tronto.net/aoc
Download | Log | Files | Refs | README

day10b.cpp (2010B)


      1 #include <iostream>
      2 #include <algorithm>
      3 #include <set>
      4 #include <string>
      5 #include <string_view>
      6 #include <vector>
      7 using namespace std;
      8 
      9 enum Direction { U = 0, D, R, L };
     10 Direction all_directions[] = {
     11 	Direction::U, Direction::D, Direction::R, Direction::L,
     12 };
     13 
     14 pair<int, int> step(pair<int, int> p, Direction d) {
     15 	auto [i, j] = p;
     16 
     17 	switch (d) {
     18 	case Direction::U:
     19 		return make_pair(i-1, j);
     20 	case Direction::D:
     21 		return make_pair(i+1, j);
     22 	case Direction::R:
     23 		return make_pair(i, j+1);
     24 	case Direction::L:
     25 		return make_pair(i, j-1);
     26 	}
     27 
     28 	return make_pair(-999,-999);
     29 }
     30 
     31 class Board {
     32 public:
     33 	const int out_of_bound = -1;
     34 	int M, N;
     35 
     36 	Board(vector<string> &lines) {
     37 		N = lines.size();
     38 		M = 0;
     39 		for (string l : lines)
     40 			M = max(M, (int)l.size());
     41 
     42 		cells = new int[M * N];
     43 		for (int i = 0; i < N; i++)
     44 			for (int j = 0; j < M; j++)
     45 				cells[M*i + j] = lines[i][j] - '0';
     46 	}
     47 
     48 	~Board() {
     49 		delete []cells;
     50 	}
     51 
     52 	int operator[](pair<int, int> p) {
     53 		int c = coord(p);
     54 		return c == -1 ? out_of_bound : cells[c];
     55 	}
     56 
     57 private:
     58 	int *cells;
     59 
     60 	int coord(pair<int, int> p) {
     61 		auto [i, j] = p;
     62 		return i >= N || i < 0 || j >= M || j < 0 ? -1 : M*i + j;
     63 	}
     64 };
     65 
     66 int reachable9(pair<int, int> p, Board& board) {
     67 	if (board[p] == 9)
     68 		return 1;
     69 
     70 	int ret = 0;
     71 	auto q = step(p, Direction::U);
     72 	if (board[q] == board[p]+1)
     73 		ret += reachable9(q, board);
     74 
     75 	q = step(p, Direction::D);
     76 	if (board[q] == board[p]+1)
     77 		ret += reachable9(q, board);
     78 
     79 	q = step(p, Direction::R);
     80 	if (board[q] == board[p]+1)
     81 		ret += reachable9(q, board);
     82 
     83 	q = step(p, Direction::L);
     84 	if (board[q] == board[p]+1)
     85 		ret += reachable9(q, board);
     86 
     87 	return ret;
     88 }
     89 
     90 int main() {
     91 	string line;
     92 	vector<string> lines;
     93 	while (getline(cin, line))
     94 		lines.push_back(line);
     95 
     96 	Board board(lines);
     97 
     98 	int tot = 0;
     99 
    100 	pair i(0, 0);
    101 	for (i.first = 0; i.first < board.N; i.first++) {
    102 		for (i.second = 0; i.second < board.M; i.second++) {
    103 			if (board[i] == 0) {
    104 				tot += reachable9(i, board);
    105 			}
    106 		}
    107 	}
    108 
    109 	cout << tot << endl;
    110 
    111 	return 0;
    112 }