Thread: 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

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.