PROBLEM LINKS
DIFFICULTY
HARD
EXPLANATION
The challenge here is to simulate Chef’s potential escape from the maze within the time constraint. For each time index from 0 until Chef faints from hunger, we calculate every position in the maze Chef could safely occupy. To advance from one time index until the next, for every safe square in the current time step, we mark all of its neighbors as safe in the next step, then mark squares that contain ghosts as unsafe, then move the ghosts, and mark their new locations as unsafe as well. Without optimizations, this approach will time out.
The key is to use bitsets to store the safe positions. Suppose we use one bitset per row of the maze. Then to simulate a north or south move, we need only apply a bitwise “or” between two rows. To simulate an east or west move, we shift the bitmask right or left. The walls of the maze can also be stored as a bitset, and a bitwise “and” operation is used to make sure Chef doesn’t try to pass through a wall. Thus it only takes O(M+C) to simulate one time step, instead of O(M * N+C).
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.