Editorial for COCI '20 Contest 4 #5 Patkice II

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.

The map can be thought of as a weighted directed graph. The nodes are cells of the map, and two nodes are connected if the corresponding cells share a side. The weight depends on the direction of the current. If the current in cell $A$ $A$ is directed towards cell $B$ $B$ (or $A$ $A$ is the initial island), the weight of edge $A \to B$ $A \to B$ is zero because we don't have to change the map to be able to go from $A$ $A$ to $B$ $B$ directly. Otherwise, we have to change one character on the map and the weight is one.

To find the minimum number of changes needed, we just need to find the distance from o to x in the described graph, which can be done with 0-1 BFS. Dijkstra's algorithm is a bit slower, but it was also enough to get all points.

The changed matrix can be constructed like this: we start in x, and in each step we take an edge whose weight is equal to the difference of the distance of its endpoints to o, and we replace the character in the current cell with the appropriate one if the weight is equal to one.

Comments

0

Badmode commented on March 10, 2022, 4:08 a.m.

I TLE using Dijkstra's, use 0-1 BFS. Also, I store the direction of where I came from while BFSing, so it's easier to construct the changed matrix.