How would I solve this problem? I was thinking of using Djikstra's but am not sure how to code it
The Cookie Monster has infiltrated your cookie factory!
You’ve 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 Monster’s 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 monster’s 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.
Logic: This is similar to the minimum path sum problem https://leetcode.com/problems/minimum-path-sum/solution/
We have to translate the room layout to the costMatrix (or timeMatrix) and then follow the same process as the above problem.