The Cookie Monster has infiltrated your cookie factory! C++ code

Youve placed cookies in a rectangular grid of rooms to try to give yourself as much time as possible to escape from the Cookie Monster (since he might mistake you for a cookie). One example grid might look like this:

 M D C . C . . C F F G G G B E E G . G . E G D E Y 

Each character represents a room. The cookie monster (M) starts in the upper left room, and you (Y) are in the lower right. Other letters represent rooms with cookies, and periods represent rooms with no cookies. Rooms are connected such that you can move up, down, left, and right from a room to go to a new room (but not diagonally.)

The Cookie Monster is distracted by all kinds of cookies, and will eat any of them, but some types of cookies slow him down more than others and are particular weaknesses of the Cookie Monster. These will be given to you as a string. The Cookie Monster takes the following amount of time to move into a new room:

If there is no cookie (M, Y, and .) : 1 Time Unit If there is a cookie, but it is not a weakness: 2 Time Units If there is a cookie, and it is a weakness : 5 Time Units

The Cookie Monster really wants to get to you (he knows you made the cookies!) He also knows where all the cookies are, and will take the fastest path to you, while being aware of his cookie weakness.

Write a function that takes in a matrix of rooms and the Cookie Monsters cookie weaknesses, and then returns how long the Cookie Monster will take to reach your location.

Only A-Z and . will be used for rooms. M will always appear only once in the upper left corner. Y will always appear only once in the lower right corner. Only A-Z will be used for weaknesses. M and Y will not be weaknesses. There will always be at least one weakness. Weaknesses may not appear in the room grid.

Example Input

For the following 5x5 room layout

M D C . C . . C F F G G G B E E G . G . E G D E Y 

The cookie monsters path through it will be different depending on his weaknesses. If he has the weaknesses CG:

[M] D C . C [.][.][C][F][F] G G G B [E] E G . G [.] E G D E [Y] 

This is his fastest path through the grid, taking the following amounts of time

M . . C F F E . Y 1 1 5 2 2 2 1 1 -> sum of 15 time units. 

However, if his weaknesses were BCD, he would take this path:

[M] D C . C [.][.] C F F G [G][G] B E E G [.][G][.] E G D E [Y] M . . G G . G . Y 1 1 2 2 1 2 1 1 -> sum of 11 time units. 

Keep in mind that the optimal path may lead the Cookie Monster to go up or left, not just down and right.

starter code:

#include #include #include #include #include

using namespace std;

/* Args: weaknesses: a string, one character for each cookie weakness. grid: a vector> describing the map layout, one char per room

Returns: An int, how many time units it will take the Cookie Monster to reach you. */ int timeToEscape(string weaknesses, const vector>& grid) { // Your code here. // NOTE: You may use print statements for debugging purposes, but you may // need to remove them for the tests to pass. return 0; };

// DO NOT MODIFY BELOW HERE int main() { string line; bool firstArg = true; vector> grid; string weaknesses;

while (getline(cin, line)) { istringstream iss(line); if (line == "") continue; if (firstArg) { firstArg = false; weaknesses = line; } else { vector v(line.begin(), line.end()); grid.push_back(v); } }

cout << timeToEscape(weaknesses, grid) << endl; }