## Editorial for SAC '22 Code Challenge 2 P4 - Cookie Galore

Remember to use this editorial

**only**when stuck, and**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.**Submitting an official solution before solving the problem yourself is a bannable offence.**Author:

First, realize that this problem asks for the shortest path from to .

Next, decompose the grid of characters into a graph:

If the next position you are travelling to is a

`.`

cell, the weight is .If the next position you are travelling to is a

`C`

cell, the weight is .

Now, run a shortest path algorithm (e.g., Dijkstra's algorithm) to find the shortest path.

**Time Complexity:**

Note that a faster time complexity can be achieved by further realizing that the weights are either or , allowing you to use 0-1 BFS.

Also, the bounds for and are relatively low because the author believes that distinguishing between a log factor (e.g., Dijkstra's algorithm vs. 0-1 BFS) is unfair to competitors.

## Comments