← All solutions

The first step is to figure out where to put the water pressure level. Or rather, to blindly try all possibilities for the water pressure, which incurs a factor of N on the running time.

Given the water level, consider the induced subgraph on the set of points that are below water. This consists of a set of connected components C₁ , . . . , C_r , which we can think of as forming a (complete, weighted) graph G, in which the distance from component C₁ to component C₂ is the minimum distance between a point in C₁ and a point in C₂ which both have an available pipe hole. We want to find a path from the component containing s (say, C₁ ), to the component containing t (say, C_r ), possibly using some intermediate components at shortcuts. The total cost of the path is the sum of distances of edges used, plus the cost of plugging the holes in the used components. The cost of plugging the holes in some intermediate component C_i is 0.5 · (#{open holes in C_i } − 2), because all holes except the two that we use to connect C_i to the previous and next component need to be plugged. Similar calculations apply for the components C₁ and C_r . Note that intermediate components must have at least two holes (and the source and destination components must have at least one hole). A special case has to be dealt with: when s and t are in the same component, no path is needed and the plugging cost is just 0.5 · #{holes in C₁ }.