-
Penalty Mazes
Hey guys,
First of all I'm seriously stuck on this assignment and literally have got no idea where to start so some much needed advice would be grateful helpful. Basically I'm stuck because I'm not entirely sure where to start. I have an algorithm to base my assignment off but I cant figure out how to replicate this in C, this algorithm is as follows:
Code:
while (not at destination &&
non-taboo adjacent cell exists)
Add current cell to visited list
Add current cell's penalty to total penalty
Mark current cell as taboo
Check if destination found
Find cheapest non-taboo adjacent cell
Check if stuck
Move to cheapest cell
we have a 12 x 12 maze to with sides of the mazes declared as taboo. help!
-
I think if you gave us your assignment statement too you would have had more chances to get an answer.
-
Don't really know what you mean but here's what the program is supposed to do, all I'm after really is a point to get me started. Basically an explanation of what the program is supposed to do as I don't have a clue.
Code:
data1 contains the following :
1 1
1 5
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 0 1 2 3 4 5 6 7 8 9 -1
-1 10 11 12 13 14 15 16 17 18 19 -1
-1 20 21 22 23 24 25 26 27 28 29 -1
-1 30 31 32 33 34 35 36 37 38 39 -1
-1 40 41 42 43 44 45 46 47 48 49 -1
-1 50 51 52 53 54 55 56 57 58 59 -1
-1 60 61 62 63 64 65 66 67 68 69 -1
-1 70 71 72 73 74 75 76 77 78 79 -1
-1 80 81 82 83 84 85 86 87 88 89 -1
-1 90 91 92 93 94 95 96 97 98 99 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
$ gcc program2.c
$ a.out data1 result1
$ cat result1
The destination was reached.
Penalty accrued : 10
1 1
1 2
1 3
1 4
$
hope that helps
-
What you are being asked to implement is a greedy algorithm which has a starting and an ending point. You could mantain at each step two current indexes(line number, column number) and the given matrix(if you don't care about memory usage) whose cells are updated to -1 when they become taboo. At each step you move through the matrix in a greedy fashion(to the neighbour with the lowest cost but different from -1) until you reach the destination. Sum up the cells you've travelled through and that is the "Penalty accrued".
From (1,1) to (1,5) you travel through (1,1) - penalty 0,(1, 2) - penalty 1,(1, 3)- penalty 2,(1, 4)- penalty 3,(1, 5) - - penalty 4. 1 + 2 + 3 + 4 = 10
-
Thanks, any ideas where i should? I still haven't got a clue how to implement this
-
Think about what data types you need to represent your maze. What about your start and end coordinates and current position? What about your total penalty?
The basic idea is to break your program down into small chunks and test as you go.
Start with something basic, like being able to read in the data file correctly. You can take data1 and result1 as parameters and practice by just reading the data file into an appropriate structure/array/etc and then write it right back into result1 for starters.
Once you can do that successfully, then you can work on your maze solving algorithm. Most of the statements in the pseudo code you provided sound like they'd make great functions (e.g. at_destination, find_cheapest_non_taboo_adjacent_cell). Maybe shorten the names a bit though. Write them one at a time, testing each as you go.
Code the body of the while loop and make sure your program works for one iteration. Then, add the loop around your maze solving algorithm, writing the steps your algorithm takes to the output file as you go.
