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