Problem Description: Stream Paths

Suppose you have a 2D array elev of integers that represent elevations on a grid. If a stream of water originates at the location with row index r and column index c, what would it do what path would it take and where would it end up? This problem is similar to problems in many areas, for example, in certain optimization techniques (steepest descent).

In this problem well make the following assumptions:

1. The elevation grid will be a n row, m column grid of integers, where n and m are constant ints. (Note: the example below uses a 7-row 5-column array; however, do not hard code 7 and 5 in your program. Instead use n and m so it will be easy to change the sizes if needed.)

2. Once the stream origins location is specified, then the stream flows to whichever of the four adjacent locations in the grid represents the largest descent. The adjacent locations are the locations (i) in the same column, but with row index decreased by 1, (ii) in the same row, but with column index increased by 1, (iii) in the same column, but with row index increased by 1, and (iv) in the same row, but with column index decreased by 1.

3. If more than one of the adjacent locations have the largest decrease, then the water flows to whichever adjacent location appears first in the last items list.

4. This process continues, with the stream flowing from location to location until it either reaches a location where none of the four adjacent locations has its elevation strictly less than that location, or until it reaches the edge of the grid (any row with index 0 or n ? 1, or any column with index 0 or m?1).

This homework asks you to solve this problem in two parts.

Problem A: A Single Step Write a C++ program that sets up a grid, and then asks a user to input an initial location. If the input location is an invalid location (row less than 0 or greater than or equal to n, or column less than 0 or greater than or equal to m ), the program should print Invalid location. Otherwise the program should call a function you should write:

bool moveToLowerElev(int elev[][m], int n, int m, int& r, int& c)

Given the row and a column for a current interior location, this function should first check ifthat location is on the edge of the grid. If it is, the function should return false. If it is not, the function should check the four adjacent locations. If none has an elevation strictly less than the current location, then the function should return false. Otherwise the function should return true, and return the row and column of the adjacent location with the least elevation 1 (using the rules above in case of a tie) through the reference parameters int& r and int& c.

If moveToLowerElev returns false, your main program should print Path ends. Otherwise, the program should print the new row and column, as well as the elevation at that new location.

Here is an example based on the following grid that has n = 7 rows and m = 5 columns.

int elev[n][m] = {{0, 0, 0, 0, 0},

{0, 1, 2, 3, 4},

{0, 2, 0, 2, 0},

{2, 3, 1, 2, 4},

{3, 4, 3, 4, 5},

{4, 5, 5, 2, 6},

{3, 3, 3, 2, 1}};

Here is an example run of the program with the origin location row 4 column 3. This location is surrounded by the values (reading clockwise starting at the location with row 3 and column 3) 2, 5, 2, and 3, so the function prints should out the following: Input the origin location (row and column): 4 3 Row 3, column 3, elevation 2 As usual, make sure your input and output follow the formatting, etc. in the example. Also, remember that the function definition of moveToLowerElev should be after main in your file. (You should follow the convention, in all your files that contain main plus other functions, that the other functions definitions should be after main.)

Problem B: The Entire Path

To begin this part, make a copy of your solution from Problem A. Work with the copy, rather than the original Problem A file in this part. This part should behave the same as Problem A, except that it should have the following three changes:

1. Have the user input a filename and read the array data from that file. (The program should print an error message and exit if the file cant be opened.) The input file format will be as follows: the first line will contain two integers, which are the number of rows and number of columns of elevation data, respectively. The next row contains the first row (row index 0) of data, the row after that contains the second row (row index 1) of data, and so on. You may assume that the file is correctly in this format, and that there will never be more than 10 rows or 10 columns of elevation data. A test file named hw04b.dat is posted below. This file contains the same elevation data as in the Problem A example. However, your program should work not only with this test file, but with any file of this type, including files with different numbers of rows or columns. Remember to close this file when your program is done with it.

2. Compute the entire stream path rather than only a single step along that path. As your program computes the path, it should print out the locations and elevations along the path (see the example below). Note this means your program will need to call moveToLowerElev repeatedly, rather than only once.

3. Have a continuation loop encompassing the part of the program after the elevation data has been read in from the file. This way the user can input as many origin locations as he or she desires. Here is an example: Please input the data file name: hw04b.dat

Input the origin location (row and column): 0 10

Invalid row or column

Enter another origin location (y/n)? y

Input the origin location (row and column): 0 2

Path ends

Enter another origin location (y/n)? y

Input the origin location (row and column): 4 3

Row 3, column 3, elevation 2

Row 3, column 2, elevation 1

Row 2, column 2, elevation 0

Path ends

Enter another origin location (y/n)? y

Input the origin location (row and column): 1 3

Row 0, column 3, elevation 0

Path ends

Enter another origin location (y/n)? n

hw04b.dat

7 5

0 0 0 0 0

0 1 2 3 4

0 2 0 2 0

2 3 1 2 4

3 4 3 4 5

4 5 5 2 6

3 3 3 2 1