About placing the keys...


0...Duplicate the data-structure holding your map, so we don't mess up the original.
1...Do a flood-fill with P(player start) as your starting node and space (the empty area) as your target color.
2...Modify the flood-fill algorithm to find doors adjacent to the empty areas that it traverses and store them in a queue. We'll call it, door-queue. I'll write the modified* flood-fill algorithm at the end of this post.
3...If door-queue is empty, return (this is the only exit. means all doors have been opened)
4...While door-queue is not empty:
5.......Set D to the front node of door-queue.
6.......Select a replacement-color painted node at random. (replacement-color are the nodes visited in the last flood-fill).
7.......Create a key of the color of the door found in D node and place it on the node selected in Step 6. Also place the same key at the same position on the ORIGINAL MAP.
8.......Remove the door from D node on the map and replace it with replacement-color, if you haven't done it already in 0 step of Modified Flood-fill.
9.......Dequeue door-queue (remove the front node).
10..Repaint all replacement-color nodes as target-color (white space).
11..Loop back to 1. Map should now be just like it was at the beginning (no replacement-color painted nodes) except that the doors examined in this cycle are replaced with white space (opened) and the keys that open them lay around. Since these doors are now white spaces, the next flood-fill will examine a bigger area of the map since it will now be able to traverse beyond them. The algorithm ends in step 3 if the last flood-fill didn't find any doors (they have all been removed, or there wasn't any in the first place).


*About Step 2. Assuming you're using the recursive implementation (you should. It's the simplest one and lite-c can handle it). Add the following zero line at the beginning: