Katkat
Back

Extend BFS maze solver with keys and arrows

MetaSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to adapt Breadth-First Search (BFS) to a state-space where the current location is augmented by a collection of keys, effectively transforming the grid into a larger, multi-layered graph.

Problem Statement

You are given an N x M grid representing a maze. You start at position (0, 0) and aim to reach a target cell marked 'T'. The grid contains the following types of tiles:

  • . (empty): Passable.
  • # (wall): Impassable.
  • K (key): When you land on this, you pick up a key. There are multiple keys in the grid, and you must collect all of them before the target 'T' becomes passable.
  • ^, v, `` (arrows): These are one-way tiles. You can only enter this cell if you move in the direction the arrow points. Once you enter an arrow cell, you are forced to move one step further in that same direction. If that forced move results in hitting a wall or going out of bounds, the path is invalid.

Write a function min_moves(grid) that returns the minimum number of steps to reach the target 'T' after collecting all keys. If it is impossible, return -1.

Constraints

  • 1 <= N, M <= 50
  • Number of keys <= 5

Example

Input: 
grid = [
  [".", "K", "#"],
  ["^", ".", "."],
  ["T", ".", "."]
]

Output: 4

Explanation: Moving right to pick up the key, then navigating back to move through the arrow (which forces a move) to reach T.

Edge Cases

  • Starting on a key.
  • The target is unreachable.
  • The forced move from an arrow leads directly into a wall.
  • Multiple arrows in a sequence.

Hints

Hint 1

Represent the state as `(row, col, key_mask)`, where `key_mask` is a bitmask tracking which specific keys have been collected.

Hint 2

When BFS reaches an arrow tile, perform the forced move immediately and add the resulting destination to the queue as a single step.

Hint 3

Ensure your visited set tracks both the coordinates and the `key_mask` to prevent cycles in the augmented state space.

Follow-up questions

  • How would your approach change if keys were consumable (i.e., used to open doors) rather than just needing all of them to unlock the exit?
  • If the grid contained teleportation pads that could move you to any other teleportation pad, how would you update the graph representation?
  • What is the time complexity of your solution in terms of N, M, and K (number of keys)?