Editorial for COCI '16 Contest 3 #2 Pohlepko
Submitting an official solution before solving the problem yourself is a bannable offence.
The solution that was good enough for of points works under the assumption that a field's right and down neighbours are different. This way, we can start from the initial field and in each step compare the neighbours - we will always move the token to a field that is alphabetically smaller.
The problem arises when both neighbours are the same. This problem can be solved by keeping track of, in each step, a list of all optimal positions in which we could have ended up after a certain amount of steps. We start with the list containing the initial field and in each step update the list so that we first check the minimal value of the neighbours of all positions in the current list, and then create a new list that will contain all neighbouring positions with that value. Since we can reach a field in ways, we must be careful not to add the same position twice to the list, because this way we would copy the number of appearances of the same position in each iteration.
Comments