In this problem, we are given a 2D array representing a grid of square tiles, some of which are blocked. We know
our source and destination positions, marked in our input by '
S' and '
T'
respectively.
This is a common scenario in which we want to know the shortest path, measured by the total number of
'
moves', from the start to finish, if and only if it is possible to reach the finish. In other
problems, you may only want to know the number of steps, where each step moving to a valid adjacent grid
location, and not care about the direction you are facing. In this problem, we must also consider our
directional heading (i.e. N, E, S, W) and may only move to adjacent and non-blocking grid locations that are
logically
in front of us. We may turn 90 degrees left or right and remain at our current location, but
this counts as a move. Finally, we must also consider the rotating color wheel, which starts on green and must
end on the green face if the path is to be considered valid.
One way of approaching this type of problem is by implementing a modified
breadth-first search (BFS). We will use a
std::queue
, and ideally we'd like to
minimize the amount of code we write and avoid having to manage memory. These problems tend to test your ability
to keep your implementation organized and not get confused. So we'd like to spend a little more time with the
setup than usual.
What is a state?
Any given state, or grid configuration, will have 4 pieces of information associated with it:
- row index
- column index
- direction (i.e. heading)
- color (on the bottom)
Our direction is always initially logical North, and our color always starts on the green face and must end on
the green face. Regarding possible values, there are 25 rows, 25 columns, 4 directions, and 5 colors.
So how many possible states are there?
25 * 25 * 4 * 5 = 12500 possible states.
This means we can represent any given state by a unique integer. By using a couple helper functions to map an
array of 4 values onto a single integer, as well as the reverse, we greatly simplify the legwork required for
this problem. So anytime you wish to examine the individual values of a given state, convert if necessary to the
array representation. Anytime you need to push states onto your BFS queue, convert if necessary to the integer
representation.
This simple trick can be applied to any problem in which you have to keep track of several pieces of
information, but still, want an easy way to take advantage of the C++ STL and stack memory.
This is only one way of organizing this problem. You could also use
std::tuple
, a user-defined
struct, or arrays of 4 elements. As long as you know the pitfalls to avoid when writing up your
solution, you have many options available. Personally, I like to map the state onto an integer because it
reduces the possibility of the dreaded
Segmentation fault and allows you to focus on implementing
the algorithm correctly. Where possible, you should attempt to rewrite and improve upon your own accepted
implementations.
Implementing our breadth-first search
In your
int main, start by reading your input and checking for the exit condition in a while loop.
To keep it simple, I declare the following global variables:
Once the input is read, including the initial board state, we will use our helper functions to map our starting
position, direction, and color onto a single integer and push it onto a
std::queue<int>.
We'll also want to initialize a boolean array
bool seen[12500], to mark whether a state has already
been visited, and an array of timestamps
int time[12500], to track the number of moves to get to
the state represented by a given index in the range [0, 12500).
Finally, we'll enter the while loop that will solve our problem via breadth-first search. The general algorithm,
in pseudocode, is as follows:
While the queue is not empty:
- store the front element in a local variable, pop it from the queue
- if the current element has been seen, skip to the next loop iteration; else mark it as seen
- if the current element is a valid solution, break the loop and output the result
- if we get to this point, the element is not a solution, so we compute the child states and push them
onto the queue
Example,
Links
C++ References