C++

Objective:

In this assignment, students will load a topographic (elevation) data into a 2D array and write functions to compute the path that requires the least overall change in elevation, from a given starting point. Then, they will display this path to the user.

Main Topics Covered:

Functions

File I/O

Problem

There are many contexts in which you want to know the most efficient way to travel over land. When traveling through mountains (let's say you're walking) perhaps you want to take the route that requires the least total change in elevation with each step you take call it the path of least resistance.

Given some topographic data, your program must calculate elevation change walk from one side of a map to the other.

Subscripts	1	2	3	4	5	6
1	3011	2900	2852	2808	2791	2818
2	2972	2937	2886	2860	2830	2748
3	2937	2959	2913	2864	2791	2742
4	2999	2888	2986	2910	2821	2754
5	2909	2816	2893	2997	2962	2798

3 Assignment Outline

3.1 Use the starting point for the first column

NOTE: You must read in your file name from the user using cin. Example:

cin >> infputfilename; ifstream f; f.open(infputfilename); 

The first number in the file will be a number between 1 and 5. This is your starting point. All following numbers consist of the elevation data.

Note: Subscripts in input and output files are matrices that are based on a standard mathematical definition, indexed from 1.

3.2 Read Data Into 2-Dimensional Array

Read your data from a file into a 2D array of doubles. Your program must first generate a 2D array of size 5 rows by 6 columns.

The data will be formatted as list of doubles separated by a space. Each number will represent an elevation at a specific point.

3.3 Generate a Path of Least Resistance

Given that the map is in a 2D grid, a walk can be defined as starting a given point on the left-most edge of the map and proceed to take a step into one of three possible points in the column to the right: top-right (), direct right (), and bottom-right ().

Formula for calculating the change in elevation of at a given prospective step:

y = |yf - yo|

yf refers to the value of the final elevation (the elevation of a prospective step)

y0 refers to the value of the initial elevation (the current elevation)

For the purposes of this assignment, you can assume that there not be a case where there will be a tie in the change of elevation (y) between your three options. Henceforth, there will only be one single path you can take.

Case 1: Smallest change in elevation. Move to the block with the least change in elevation

	101
100	107
	102

Smallest change is 1, move to the top right ()

Additionally, your program must use at least this function:

double difference(double array[5][6], int r, int c, int r1, int c1){

/implementation not shown/

}

This function must return the change in elevation between the current point and a prospective step

Ex. If I am at point (row 2, col:1) and am thinking about going to (3,2), difference() should return 5.0

	109
100	107
	105

You may use additional functions in your code to improve readability and reusability.

3.4 Display the lowest elevation change path

Print the path to a file called out.txt by printing each node that is visited in a new line. Note

Each line should follow this format:

row,column:value

*Note: There are no spaces between these values *

4 Example Input and Outputs Note: Subscripts in input and output files are matrices that are based on a standard mathematical definition, indexed from 1.

4.1 Example 1

Input:

3

3011 2900 2852 2808 2791 2818

2972 2937 2886 2860 2830 2748

2937 2959 2913 2864 2791 2742

2999 2888 2986 2910 2821 2754

2909 2816 2893 2997 2962 2798

Output:

3,1:2937

2,2:2937

3,3:2913

4,4:2910

5,5:2962

5,6:2798

4.2 Example 2

Input:

1

3011 2900 2852 2808 2791 2818

2972 2937 2886 2860 2830 2748

2937 2959 2913 2864 2791 2742

2999 2888 2986 2910 2821 2754

2909 2816 2893 2997 2962 2798

Output

1,1:3011

2,2:2937

3,3:2913

4,4:2910

5,5:2962

5,6:2798

4.3 Example 3

Input:

2

10.1 434.2 1345.43 3423.4 1234.5 16650.6

12.2 123 3222 42343 4123123 5123

44.44 33.22 5452.1234 2134.22 234.22 855.33

33.33 55.55 1 21 69 420

1010.30 5050.44 45223.33 33333.33 32111.11234 333.444

Output

2,1:12.2

3,2:33.22

4,3:1

4,4:21

4,5:69

5,6:333.444

Bonus

Improve your program by implementing a tie breaker mechanism for cases where the change of elevation (y) between two of your three options are equal.

Case 2: Tie in the change in elevation and direct right () is an option, so go to the directly right ()

Case 3: Tie in the change in elevation and direct right () is not an option, choose bottom right ()

	97
97	97
	105

Case 2: Smallest change is a tie, but direct right () is an option, move to the direct right ()

	105
97	107
	105

Case 3: Smallest change is a tie, but direct right () is not option, to the bottom right ()

The bonus will be tested on an additional test case and it will be worth 10 points if implemented correctly. If you attempt implementing the bonus, be sure that it does not compromise the rest of the program!