Minimum Moves to Reach Target with Rotations

Minimum Moves to Reach Target with Rotations

1. What is this problem about?

In this "Hard" grid problem, you control a snake that occupies two adjacent cells. The snake can be either horizontal or vertical. Your goal is to move the snake from its starting position (top-left, horizontal) to the target position (bottom-right, horizontal) in the minimum number of moves.

The snake can:

• Move right or down (if both cells it will occupy are empty).
• Rotate 90 degrees clockwise or counter-clockwise (if the $2 \times 2$ area involved is empty).

2. Why is this asked in interviews?

Kakao and other gaming/logistics companies use this to test BFS on a complex state. Key skills:

• State Representation: The state isn't just (x, y), but (x, y, orientation).
• Validation: Checking the $2 \times 2$ space for rotations.
• BFS Implementation: Managing the queue and visited set for this 3D state space.

3. Algorithmic pattern used

The pattern is BFS.

• State: (r, c, is_vertical), where (r, c) is the coordinate of the "head" or the top-left-most cell of the snake.
• Queue: Standard BFS queue for shortest path.
• Transitions:
  • Move Right: Valid for both orientations if the target cells are empty.
  • Move Down: Valid for both orientations if the target cells are empty.
  • Rotate: Only valid if the $2 \times 2$ block containing the snake and its rotation target is empty.

4. Example explanation

Snake at (0, 0) and (0, 1). Horizontal.

• Move Right: Now at (0, 1) and (0, 2).
• Move Down: Now at (1, 0) and (1, 1).
• Rotate: Now at (0, 0) and (1, 0). (Only if (1, 1) is also empty). The BFS explores these states layer by layer until the snake's tail reaches the target cell.

5. Common mistakes candidates make

• Incorrect Rotation Logic: Only checking the target cell for rotation instead of the entire $2 \times 2$ area.
• Visited Set: Forgetting that (r, c, horizontal) and (r, c, vertical) are different states.
• Off-by-one: Miscalculating the position of the tail relative to the head.

6. Interview preparation tip

Practice "Object movement" BFS problems. When the "player" occupies more than one cell, define the state based on one "anchor" cell and an orientation. This keeps the coordinate math consistent.