← All solutions

This is the second problem in the set involving a triangulated surface with elevations, but apart from that similarity this problem is quite different.

A conceptually simple approach is the following. First identify all regions (i.e., the triangles and the boundary). Then build a graph where two regions are connected if they share a side. Now, using e.g., Dijkstra’s algorithm, compute for each triangle, the smallest possible maximum height along any path to the boundary (where the height of an edge is the minimum of the two endpoints of the shared side corresponding to the edge). Finally, we can reconstruct the lakes as follows: each triangle where the smallest maximum height is larger than the minimum depth of the three points of the triangle must be part of a lake having a depth equal to the smallest maximum height. Doing a DFS or BFS from this triangle finds us all the triangles that are part of this lake. There are a few steps but none of the steps are very difficult.