Description
Requirements
This rst assignment lets you get familar with submission of a simple (but correct and e cient) algorithm to the CompSci 320 automated marker. This assignment tests your ability to process and model input for a real-world-like problem. You should already have su cient algorithmic skills from the prerequisite course CompSci 220 to complete this assignment.
It is worth 5% of your total course marks. (Note future programming assignments will require much more work to obtain the same number of marks so you are encouraged to make a serious attempt on this one.)
Problem: Shortest Cost Route to Navigate a Grid
Consider a grid where each cell has a di erent cost to travel across the regions. Assume we can only travel and stop in straight lines between the corners of these cells. Note that the cost to travel along a border between two cells is the cheapest of the two. We want to nd the cheapest route from the lower-left corner to the upper-right corner of the grid under these constraints.
For example in the following 3 3 grid, one of the cheapest routes of cost 2+3+4+2=11 is highlighted.
We will read in a sequence of problem instances. The rst line will contain two positive integers n and m, both at most 400, denoting the dimensions of the grid; here the number of rows is n and the number of columns is m. We then are given n lines of m non-negative integers representing the costs for the cells. All integers will be separated by spaces. The last problem instance will have values of n = m = 0, which is not processed.
The input should be taken from keyboard/stdin/System.in.
Sample Input:
|
3 |
3 |
|||
|
0 |
6 |
2 |
||
|
1 |
8 |
4 |
||
|
2 |
3 |
7 |
||
|
3 |
5 |
|||
|
1 |
3 |
9 |
9 1 |
|
|
5 |
10 |
1 8 |
4 |
|
|
2 7 |
8 2 |
6 |
||
|
0 |
0 |
The output for each instance should be a single integer (one per line) denoting the minimum cost to travel. Print these to the console/stdout/System.out.
Sample Output:
11
17
1
For this assignment you need to submit a single Python source program. There will be three inputs of several test cases of increasing di culty. You can resubmit up to 10 times to http://www.automarker. cs.auckland.ac.nz/. There are two marks awarded for test cases 1 and 2 and one mark awwarded for test case 3.
2
