CS1101C Practical Exam

Session 3 (1400 - 1545 hours)

Find A Path

The name of your C program file must be scrat.c, files with any other name will not be marked.

The deadline for this lab is Wednesday 12 April 2006, 15:45:59 hours. Strictly no submissions will be accepted after the deadline.

Background

Scrat, a sabre-toothed squirrel of Ice Age fame, needs to carry his acorn through a hilly valley and he needs your help. Being of small brain, he is not able to find the best path through the valley. The "best path" is defined to be the path that minimizes his total walking effort (remember that he still needs to guard his acorn jealously!). To simplify our problem, we will find a good path which is not necessarily the best or shortest path.

Task

Scrat's world is modeled by an NxN matrix, and Scrat's task is to walk from point (0, 0) to point (N-1, N-1). Each entry of the matrix contains a number between 0 to 100 inclusive, which represent the level of walking difficulty (0 = easiest, 100 = hardest). Your task is to write a program that automatically finds a good path through Scrat's world, so that he can minimize his walking effort and maximize his efforts to guard his acorn.

Your program should begin by asking the user for the size N (2 <= N <= 25) of the world (Scrat's world is always square), and then fill the entries with random integer values between 0 and 100. So suppose that the user wants a 4x4 world, and your program generated the following matrix, where (0,0) is the top left hand corner and (0,3) is the top right hand corner:

25 17 100 100
75 100 15 100
100 100 100 22
100 100 100 80

Your program should now print his path in terms of (row, column) coordinates, and print out his total walking effort. So in the example above, your program would print out this (please follow the sample output precisely):

Scrat should walk from:

(0, 0) to (0, 1)
(0, 1) to (1, 2)
(1, 2) to (2, 3)
(2, 3) to (3, 3)

His walking effort is 159.

Note that in order for your program to be correct, it must start from (0, 0) and end at (N-1, N-1), regardless of the cost at (N-1, N-1). Scrat's movements are also restricted: At each point, he can only either go right (e.g. from (0, 0) to (0, 1)), down (e.g. from (0, 0) to (1, 0)), or diagonally right (e.g. from (0, 0) to (1, 1)); you are to choose the square with the least cost.

Sample Output

Here is a sample run (user's input is in bold):

Please enter N: 4

Please enter the seed: 8518

Scrat's world:
9   1   99  51
54  18  11  48
57  33  74  50
35  76  96  2

Scrat should walk from:

(0, 0) to (0, 1)
(0, 1) to (1, 2)
(1, 2) to (1, 3)
(1, 3) to (2, 3)
(2, 3) to (3, 3)

His total walking distance is: 121

You are reminded to follow the sample output exactly; else marks will be deducted. Note that you may not get exactly the same answer even if you use the same seed value.

Do not use any structures or File I/O in your program, else no credit will be given.

Remember to submit your program using the submit scrat.c command, and check your submission using the check command.

All the best!

UNIX commands

Some useful UNIX commands (in case you forgot what you did in Lab 0):

  1. “dir”: lists all the files in the directory.
  2. “cp a.txt b.txt”: copies a.txt to b.txt.
  3. “mv a.txt b.txt”: moves / renames a.txt to b.txt.
  4. “cat a.txt”: shows the contents of a.txt.