Programming Language: C++

Examine the following problem:

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.

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".