diff options
| -rw-r--r-- | 22.12/main.cpp | 32 |
1 files changed, 32 insertions, 0 deletions
diff --git a/22.12/main.cpp b/22.12/main.cpp index 110cf15..5c7519e 100644 --- a/22.12/main.cpp +++ b/22.12/main.cpp @@ -74,8 +74,40 @@ part1() } int +part2() +{ + bool visited[h][w] = {0}; + deque<Point> frontier; + frontier.push_back(goal); + + 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 (h2 + 1 < h1) continue; + visited[n.y][n.x] = true; + if (h2 == 0) return n.v; + frontier.push_back(n); + // cout << n.x << " " << n.y << " " << n.v << endl; + } + } + return -1; +} + +int main() { readInput(); cout << part1() << endl; + cout << part2() << endl; } |