Expand description
§Smoke Basin
Part two is the classic flood fill algorithm with a
twist to return the size of the filled area. This algorithm can be implemented either as a
DFS using recursion or as a
BFS using an auxiliary data structure
such as a VecDeque.
This solution uses a DFS approach as it’s faster and Rust’s stack size limit seems enough
to accommodate the maximum basin size. While we could use the Grid and Point modules
to take in the original grid one line at a time with 2D coordinates, it turns out to be
somewhat faster to instead just operate on a 1D array with an explicit border, where newline
is treated the same as '9', in order to eliminate bounds checking. We can also tweak the
flood fill to track the lowest value seen along the way, to share the work between part
one and part two.