Stranded Robot#12809

Stranded Robot (Editorial)

Author:

Vladimir Olteanu

Developer:

Vladimir Olteanu

Editorialists:

Vladimir Olteanu and Roman Bilyi

For the sake of simplicity, we will be assuming that M = N = P.

The key insight is that the robot can only attach itself to blocks that can be lit. For each of the directions from which the sun can shine, there are at most N^2 blocks that can be lit. The rest of the blocks make no difference whatsoever, and can be ignored.

Let us consider what happens when the sun is shining along the positive direction of the axis. In order to determine which blocks are lit, we will need to compute the depth buffer , where zMin[x, y] is the minimal coordinate of all the blocks that share the same and , or if no such block exists.

From this perspective, the moves available to a robot located at (x, y, z) are:

  • If z + 1 = zMin[x, y], the robot is resting on top of a block, and can move to (x \pm 1, y, zMin[x \pm 1, y] - 1) or (x, y \pm 1, zMin[x, y \pm 1] - 1) if the at the destination is greater or equal to z + 1.

  • If z + 1 < zMin[x, y], the robot can fall to (x, y, zMin[x, y] - 1).

When the sun is shining along the negative direction of the axis, we compute the depth buffer instead, where zMax[x, y] is the maximal coordinate of all the blocks that share the same and , or if no such block exists. The moves available are:

  • If z - 1 = zMax[x, y], the robot can move to (x \pm 1, y, zMax[x \pm 1, y] + 1) or (x, y \pm 1, zMax[x, y \pm 1] + 1) if the at the destination is less or equal to z - 1.

  • If z - 1 > zMax[x, y], the robot can fall to (x, y, zMax[x, y] + 1).

These statements can be generalized for the other two axes.

There are at most 6N^2 cells that the robot can visit, and the shortest path to the teleporter can be found using BFS. This solution works in O(N^2) after reading the input. The total complexity is O(N^3) and the memory usage is O(N^2).