assignment is attached below
ECE36800 Programming Assignment 3 Due Saturday, December 11, 2021, 11:59pm This assignment covers learning objective 4: An ability to apply graph theoretic techniques, data struc- tures, and algorithms for problem solving; learning objective 5: An ability to design and implement appro- priate data structures and algorithms for engineering applications. Grid traversal This programming assignment is to be completed on your own. You will implement a program that involves finding a fastest way to travel from a location at the top of a grid and exit at a location at the bottom of the grid. Consider the following 4×5 (or 4-rows-by-5-rows) grid: 4 2 1 0 5 2 0 4 1 0 4 2 2 2 7 1 7 2 9 2 We label the rows from top to bottom 0 to 3 and the columns from left to right 0 to 4. Let the coordinates of location i be (ri,ci), where ri is the index of the row that i is in, and ci is the index of the column that i is in. The highlighted (2,1)-location of the grid, for example, stores the a non-negative value of 2 (stored as short). The value at a location corresponds to the amount of time a visitor has to spend there once the visitor enters that location. After spending that amount of time at that location, the visitor moves to one of its adjacent locations. If a visitor enters the (2,1)-location at time t, the earliest the visitor can leave that location and enter a location adjacent to (2,1) is at time t +2. If a visitor enters the (1,1)-location, which stores the value 0, at time t, the visitor can immediately exit that location and enter a location adjacent to (1,1) at time t. Two locations, i of coordinates (ri,ci) and j of coordinates (r j,c j), are adjacent if r j = ri −1 ( j is above i), r j = ri + 1 ( j is below i), c j = ci + 1 ( j is to the right of i), or c j = ci − 1 ( j is to the left of i). For the (2,1)-location, the adjacent neighbor above it is the (1,1)-location, the adjacent neighbor below it is the (3,1)-location, the adjacent neighbor to its right is the (2,2)-location, and the adjacent neighbor to its left is the (2,0)-location. For the boundary locations in the grid, they do not have four adjacent neighbors. They have only two adjacent neighbors (for the corner entries) or three adjacent neighbors (for the non-corner boundary entries). For the given 4×5 grid, a visitor must enter the grid at one of the (0, i)-locations, 0 ≤ i ≤ 4. It must exit the grid at one of the (3, j)-locations, 0 ≤ j ≤ 4. Suppose a visitor enters the grid at the (0,0)-location at time 0, the values stored in the following table show the respective earliest times when the visitor could enter the corresponding locations in the given grid: 0 4 6 7 7 4 6 6 7 8 6 6 8 8 8 10 8 10 10 15 For the entrance at the (0,0)-location at time 0, the highlighted path of (0,0)→ (1,0)→ (2,0)→ (3,0) allows the visitor to exit the grid at the (3,0)-location the earliest in 11 time units. The visitor arrives at the (3,0)-location the earliest in 10 time units, as shown in the preceding table, spends 1 unit of time there before exiting. This path contains 4 locations in the grid. ECE36800 Purdue University 1 Suppose a visitor enters the grid at the (0,1)-location at time 0, the values stored in the following table show the respective earliest times when the visitor could enter the corresponding locations in the given grid: 2 0 2 3 3 2 2 2 3 4 4 2 4 4 4 8 4 6 6 11 For the entrance at the (0,1)-location at time 0, the highlighted path of (0,1) → (1,1) → (2,1) → (2,2)→ (3,2) allows the visitor to exit the grid at the (3,2)-location the earliest in 8 time units. Suppose a visitor enters the grid at the (0,2)-location at time 0, the values stored in the following table show the respective earliest times when the visitor could enter the corresponding locations in the given grid: 3 1 0 1 1 3 3 1 1 2 5 3 4 2 2 9 5 6 4 9 For the entrance at the (0,2)-location at time 0, the highlighted path of (0,2) → (0,3) → (1,3) → (2,3)→ (2,2)→ (3,2) allows the visitor to exit the grid at the (3,2) location the earliest in 8 time units. The following table is obtained using the (0,3)-location as the entry point. The visitor could exit the grid in 7 time units at the (3,2)-location. 3 1 0 0 0 3 3 1 0 1 5 3 3 1 1 9 5 5 3 8 The following table is obtained using the (0,4)-location as the entry point. The visitor could exit the grid in 12 time units at the (3,2)-location. 8 6 5 5 0 8 8 6 5 5 10 8 8 6 5 14 10 10 8 12 There is another fastest path when the entry point is the (0,4)-location, as highlighted below: 8 6 5 5 0 8 8 6 5 5 10 8 8 6 5 14 10 10 8 12 Among all these entry points, the entry point at the (0,3)-location allows a visitor to enter the grid at the top and exit the grid at the bottom at the (3,2)-location the earliest in 7 time units. The corresponding path is (0,3)→ (1,3)→ (2,3)→ (2,2)→ (3,2), which contains 5 locations in the grid. Deliverables In this assignment, you are required to develop include file(s) and source file(s) that can be compiled with the following command: gcc -std=c99 -pedantic -Wvla -Wall -Wshadow -O3 *.c -o pa3 It is recommended that while you are developing your program, you use the “-g” flag instead of the “-O3” flag for compilation so that you can use a debugger if necessary. The executable pa3 should be run as follows: ECE36800 Purdue University 2 ./pa3 binary grid file text grid file fastest times file fastest path file Given a 2-dimensional grid stored in the (binary) input file binary grid file, the program produces three output files: text grid file stores the input grid in text form, fastest times file stores the fastest time to exit the grid at the bottom for each entry location at the top of the grid, and fastest path file stores the fastest path that allows a visitor to enter a location in the top row of the grid and exit at a location in the bottom row of the grid the earliest possible. Both fastest times file and fastest path file should be binary. Binary grid file format The binary grid file argv[1] is an input file in binary format. Given a grid of m rows and n columns, 0