Programming Language: C++

Consider a rectangle grid of rooms, where each room may or may not have doors on the North, South, East, and West sides. Starting from the center (x) room, find a way out of the grid.

		x

Not every room has 4 doors. The path will not be direct. Only the four corner rooms how outside doors. Use the following array of room configurations:

	0	1	2	3	4
0	{1,0,1,0}	{0,0,1,1}	{0,0,1,1}	{0,1,0,1}	{0,0,1,0}
1	{0,1,0,0,}	{0,0,1,0}	{0,0,1,1}	{1,0,1,1}	{0,1,0,1}
2	{1,1,0,0}	{0,0,1,0}	{0,1,0,1}	{0,1,1,0}	{1,1,0,1}
3	{1,0,1,0}	{0,1,1,1}	{1,1,1,1}	{1,0,0,1}	{1,0,0,0}
4	{0,1,0,0}	{1,0,1,0}	{0,0,1,1}	{0,0,0,1}	{0,0,1,0}

The rooms are listed in a 2-dimentional array with the rows as the first dimension, columns second. [0,0] is the upper-left room, [4,0] the lower-left. The middle (blue) room is [2,2]. The doors are listed in order: North (up), South (down), East (right), and West (left). If a door exists, the array contains the number 1. 0 means no door exists for that direction.

3. Write a recursive algorithm that searches each room until a way out is found. The function should return a list of the working path. The path should contain the direction traveled out of each room.

For example, the first successful move will be South from room [2,2]. That value can be represented as number 1 (North = 0, South = 1, East = 2, West = 3). When completed, the list may look like "1, 2, 0, 2, 0, 3, 0, 3, 3, 3, 0". Hint: You may wish to draw a picture of the grid in order to help you understand it. Here is some simple psuedocode that may help:

function success = find_way_out( maze, room ) for every door in the room new_room = go_through_door( maze, door ) if ( find_way_out ( maze, new_room ) ) take that door. end end end

4. Display a blank line and pause before closing the program.