Lab 6: More SLR

Problem 1: Wrap up your ideas from last time and write detailed pseudocode for SLR-flooding a terrain.

The inputs to the algorithm are a grid DEM, and an arbitrary sea-level rise x. The output is a grid of the same size and extent, in which every point will be set as:

• 1 if it was initially land and floods when the sea level rises by x feet;
• 0 otherwise.

Note that the way we defined the output: Only land points that get under water are considered flooded . Points that are initially sea are not considered flooded so they are marked as 0.

Problem 2: There are two ways to model the flooding above: recursive, and with a queue. Whichever one you came up with, consider the other one. The approach with a queue is perhaps more intuitive because it resembles BFS. In fact, it is BFS. The typical BFS starts from one point, this one starts from all points on the boundary that are sea (called a multi-source BFS).

Problem 3: Consider a more general problems:

• Given a point p = (i, j) in the grid, what is the minimum rise x which floods p?
• Do this for the entire grid: find the level at which p floods, for all point p=(i, j) in the grid

Hint: Generalize the BFS from above, and express this as a shortest-path problem. A path on a grid consists of cells.

• Consider a path between the sea and a cell p. Imagine the water coming to p along this path, and flooding this path until reaching p. Which cell along this path tells us at what level will p flood?
• Use this to define the cost of a path
• Of all paths from p to the sea, which one do we want?