Previous Next

Constrained Maze Shortest Path

TCS NQT Coding Medium Go Ad-Free - ₹20/mo

Given a 2D grid maze where each cell has a value: 0 (open), 1 (obstacle), 2 (special block), or 3 (dangerous block). Find the shortest path from the start coordinates to the target coordinates, moving only up, down, left, or right (no diagonals). The path must not pass through obstacles (value 1), must not visit any cell more than once, can include at most two cells with value 2, and must avoid cells with value 3 unless it is the only possible way to reach the target. If multiple paths exist, minimize the number of dangerous blocks (value 3) crossed. Return the length of the shortest path as an integer, or the string "STUCK" if no valid path exists.

Examples:

Input: Maze = [[0,0,0,0,0], [0,1,0,1,0], [0,2,2,2,0], [1,1,1,1,0], [0,0,0,0,0]], Start = (0, 0), Target = (4, 4)

Output: 8

Input: Maze = [[0,0],[0,0]], Start = (0, 0), Target = (1, 1)

Output: 2

Input: Maze = [[0,1],[3,0]], Start = (0, 0), Target = (1, 1)

Output: 2

Constraints

  • The maze is an M x N grid with 1 ≤ M, N ≤ 100.
  • Cell values are integers in {0, 1, 2, 3}.
  • Start and target coordinates are within grid boundaries.
  • Moves are restricted to up, down, left, right (no diagonals).
  • Cannot pass through cells with value 1 (obstacles).
  • Cannot revisit any cell in the path.
  • Path can contain at most two cells with value 2.
  • Minimize crossing cells with value 3; only cross if unavoidable to reach target.