diff options
| -rw-r--r-- | 22.12/main.cpp | 81 |
1 files changed, 81 insertions, 0 deletions
diff --git a/22.12/main.cpp b/22.12/main.cpp new file mode 100644 index 0000000..110cf15 --- /dev/null +++ b/22.12/main.cpp @@ -0,0 +1,81 @@ +#include <algorithm> +#include <cstddef> +#include <deque> +#include <iostream> +#include <string> +using namespace std; + +static constexpr size_t w = 132, h = 42; +static uint8_t heights[h][w]; + +struct Point {int x, y, v;}; +Point start, goal; + +void +readInput() +{ + for (auto &r : heights) { + fill(begin(r), end(r), 255); + } + int y = 0; + for (string line; getline(cin, line); ) { + if (h <= y) throw "bad input"; + for (int x = 0; x < line.size(); x++) { + if (w <= x) throw "bad input"; + char c = line[x]; + if (c == 'S') { + start.x = x; + start.y = y; + start.v = 0; + c = 'a'; + } else if (c == 'E') { + goal.x = x; + goal.y = y; + goal.v = 0; //unused + c = 'z'; + } + heights[y][x] = c - 'a'; + } + y++; + } +} + +int +part1() +{ + bool visited[h][w] = {0}; + deque<Point> frontier; + frontier.push_back(start); + + while (!frontier.empty()) { + Point p = frontier[0]; + frontier.pop_front(); + for (auto n : { + Point{p.x + 1, p.y , p.v + 1}, + Point{p.x - 1, p.y , p.v + 1}, + Point{p.x , p.y + 1, p.v + 1}, + Point{p.x , p.y - 1, p.v + 1}, + }) { + if (!(0 <= n.x && n.x < w && 0 <= n.y && n.y < h)) + continue; + if (visited[n.y][n.x]) continue; + auto h1 = heights[p.y][p.x]; + auto h2 = heights[n.y][n.x]; + if (h1 + 1 < h2) continue; + visited[n.y][n.x] = true; + if (n.x == goal.x && n.y == goal.y) { + return n.v; + } + frontier.push_back(n); + // cout << n.x << " " << n.y << " " << n.v << endl; + } + } + return -1; +} + +int +main() +{ + readInput(); + cout << part1() << endl; +} |