Editorial for COCI '12 Contest 4 #3 Voyager


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 solution to this task is an implementation of the given conditions. Let us describe some characteristics of the solution.

At the start, the probe is located in the given position. We have to send the signal in all four directions (up, right, down, left). We must keep the current position and the current direction. Once the signal encounters a planet, it changes its direction.

We keep the current direction as a value marked d (d = 0, up; d = 1, right; d = 2, down; d = 3, left). Let us create two arrays of length 4 like this: RS = [-1, 0, 1, 0] and CS = [0, 1, 0, -1]. Notice that RS[d] is the shift in rows, and CS[d] is the shift in columns.

After we check the value in the current cell, we might have to do a direction correction. We repeat this procedure until the signal leaves the system or until it encounters a black hole. We perform a direction change using bitwise XOR, like this:

if planet = '\' then
    d = d XOR 3
if planet = '/' then
    d = d XOR 1

It is easy to check that the above described direction change is correct.

The additional problem is determining a situation in which the signal enters a cycle. We do that by counting the cells we have already visited. Given that a signal can travel through a cell in four directions, and the system has N \times M cells, there are 4 \times N \times M positions in which the signal can be. When a signal visits more cells than that, it is obviously in a position where it had been before. The next position depends on the current position only, so the signal is in a cycle.


Comments

There are no comments at the moment.