Editorial for COCI '07 Contest 4 #6 Kocke
Submitting an official solution before solving the problem yourself is a bannable offence.
This task can be solved in many ways and with different strategies, but various cases can seriously complicate solutions. The solution described here is considered simplest by the author, in terms of coding complexity and how many special cases need handling.
The gist of the solution is a subroutine which moves a specific cube (which hasn't yet joined another cube) to some pair of coordinates, making sure the cube does not join other cubes en route (except perhaps when arriving at its destination), and that the robot does not move any other cube.
The subroutine uses breadth-first search. The state is two pairs of coordinates, the coordinates of the robot and the cube it is moving. See the sample source code for implementation details.
After the subroutine is done, we need to analyze the starting situation:
- The robot can reach every square without pushing cubes.
- The robot is trapped and cannot move without moving cubes.
- The robot can't reach every square without pushing – some square is surrounded by four cubes.
Case 3 is solved by pushing the upper of those four cubes one square down (using the subroutine). Now we already have four cubes joined forming the upper part of the letter T
, so we simply move the remaining cube (again using the subroutine) to complete the letter.
Case 2 is converted into case 1 with one push. We need to make sure the push doesn't join two cubes.
Finally, case 1 is solved by choosing the final coordinates of the letter T
(for example, , , , and ) and then bringing the five cubes to the five coordinates with five calls of the subroutine.
If we always choose the cube with the largest x-coordinate as the cube to move next, then there will always exist a sequence of moves to bring it to its final coordinates, since the robot can reach every square without pushing cubes (including the square immediately to the left of the cube), and after that we no longer need to worry about the cube joining other on the way to its final destination.
Comments