Editorial for COCI '12 Contest 4 #3 Voyager
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 (, up; , right; , down; , left). Let us create two arrays of length like this: and . Notice that is the shift in rows, and 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 cells, there are 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