#include #include #include #include #include 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 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; }