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.

Editorial

Intuition:

The key insight is to model the problem as a shortest path search with additional state variables to track the number of special blocks (value 2) used so far and the number of dangerous blocks (value 3) encountered. Since we must minimize dangerous blocks first and then path length, we use Dijkstra’s algorithm with a priority queue that orders states by (dangerous_count, steps). The state consists of current coordinates, count of special blocks used, and the count of dangerous blocks. Obstacles (value 1) are never traversed, and we limit special blocks to at most two.

Approach:

Initialize a priority queue (min-heap) with the start state: (dangerous=0, steps=0, start_x, start_y, special=0).
Maintain a 3D array or dictionary best[x][y][s] storing the minimal (dangerous, steps) for each cell and special count. This implicitly avoids cycles because revisiting a cell with the same or higher cost is pruned.
For each state popped from the queue:
- If current cell is the target, return the step count.
- If a better state (lower dangerous or same dangerous with fewer steps) for (x,y,s) has been processed, skip.
- For each valid neighbor (up, down, left, right):
  - Skip if obstacle (value 1).
  - Update special count if cell is value 2 (only if <=2).
  - Increment dangerous count if cell is value 3.
  - If the new state (nx, ny, new_s, new_d) improves best[nx][ny][new_s], update and push to queue.
If the queue empties without reaching the target, return "STUCK".

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;
const int MAX = 100;

struct State {
    int d, steps, x, y, s;
    bool operator<(const State& other) const {
        if (d != other.d) return d > other.d;
        return steps > other.steps;
    }
};

int constrainedMazeShortestPath(vector<vector<int>>& maze, vector<int>& start, vector<int>&& target) {
    int m = maze.size(), n = maze[0].size();
    // best[x][y][s] = pair(dangerous, steps)
    vector<vector<vector<pair<int,int>>> best(m, vector<vector<pair<int,int>>>(n, vector<pair<int,int>>(3, {INF, INF})));
    priority_queue<State> pq;
    int sx = start[0], sy = start[1];
    int tx = target[0], ty = target[1];
    best[sx][sy][0] = {0, 0};
    pq.push({0, 0, sx, sy, 0});
    int dirs[4][2] = {{-1,0}, {1,0}, {0,-1}, {0,1}};
    while (!pq.empty()) {
        State cur = pq.top(); pq.pop();
        int x = cur.x, y = cur.y, s = cur.s, d = cur.d, steps = cur.steps;
        if (x == tx && y == ty) return steps;
        if (make_tuple(d, steps) > make_tuple(best[x][y][s].first, best[x][y][s].second)) continue;
        for (auto& dir : dirs) {
            int nx = x + dir[0], ny = y + dir[1];
            if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
            int cell = maze[nx][ny];
            if (cell == 1) continue; // obstacle
            int new_s = s;
            int new_d = d;
            if (cell == 2) {
                new_s++;
                if (new_s > 2) continue;
            }
            if (cell == 3) new_d++;
            int new_steps = steps + 1;
            auto& cur_best = best[nx][ny][new_s];
            if (new_d < cur_best.first || (new_d == cur_best.first &;& new_steps < cur_best.second)) {
                cur_best = {new_d, new_steps};
                pq.push({new_d, new_steps, nx, ny, new_s});
            }
        }
    }
    return -1; // unreachable
}

int main() {
    // Example usage
    vector<vector<int>> 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}};
    vector<int> start = {0,0};
    vector<int> target = {4,4};
    int result = constrainedMazeShortestPath(maze, start, target);
    if (result == -1) cout << "STUCK" << endl;
    else cout << result << endl;
    return 0;
}
import java.util.*;

public class ConstrainedMazeShortestPath {
    static class State implements Comparable<State> {
        int d, steps, x, y, s;
        State(int d, int steps, int x, int y, int s) {
            this.d = d; this.steps = steps; this.x = x; this.y = y; this.s = s;
        }
        public int compareTo(State other) {
            if (d != other.d) return Integer.compare(d, other.d);
            return Integer.compare(steps, other.steps);
        }
    }

    public static String constrainedMazeShortestPath(int[][] maze, int[] start, int[] target) {
        int m = maze.length, n = maze[0].length;
        // best[x][y][s] = int[]{minDangerous, minSteps}
        int[][][] best = new int[m][n][3];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < 3; k++) {
                    best[i][j][k] = new int[]{Integer.MAX_VALUE, Integer.MAX_VALUE};
                }
            }
        }
        PriorityQueue<State> pq = new PriorityQueue<>();
        int sx = start[0], sy = start[1];
        int tx = target[0], ty = target[1];
        best[sx][sy][0] = new int[]{0, 0};
        pq.add(new State(0, 0, sx, sy, 0));
        int[][] dirs = {{-1,0}, {1,0}, {0,-1}, {0,1}};
        while (!pq.isEmpty()) {
            State cur = pq.poll();
            int x = cur.x, y = cur.y, s = cur.s, d = cur.d, steps = cur.steps;
            if (x == tx && y == ty) return String.valueOf(steps);
            if (d > best[x][y][s][0] || (d == best[x][y][s][0] && steps > best[x][y][s][1])) continue;
            for (int[] dir : dirs) {
                int nx = x + dir[0], ny = y + dir[1];
                if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
                int cell = maze[nx][ny];
                if (cell == 1) continue; // obstacle
                int new_s = s;
                int new_d = d;
                if (cell == 2) {
                    new_s++;
                    if (new_s > 2) continue;
                }
                if (cell == 3) new_d++;
                int new_steps = steps + 1;
                int[] cur_best = best[nx][ny][new_s];
                if (new_d < cur_best[0] || (new_d == cur_best[0] && new_steps < cur_best[1])) {
                    cur_best[0] = new_d;
                    cur_best[1] = new_steps;
                    pq.add(new State(new_d, new_steps, nx, ny, new_s));
                }
            }
        }
        return "STUCK";
    }

    public static void main(String[] args) {
        int[][] 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}};
        int[] start = {0,0};
        int[] target = {4,4};
        System.out.println(constrainedMazeShortestPath(maze, start, target));
    }
}
import heapq

def constrained_maze_shortest_path(maze, start, target):
    m, n = len(maze), len(maze[0])
    # best[x][y][s] = (dangerous, steps)
    best = [[[(float('inf'), float('inf')) for _ in range(3)] for _ in range(n)] for _ in range(m)]
    sx, sy = start
    tx, ty = target
    best[sx][sy][0] = (0, 0)
    heap = [(0, 0, sx, sy, 0)]  # (dangerous, steps, x, y, special)
    dirs = [(-1,0), (1,0), (0,-1), (0,1)]
    while heap:
        d, steps, x, y, s = heapq.heappop(heap)
        if (x, y) == (tx, ty):
            return steps
        if (d, steps) > best[x][y][s]:
            continue
        for dx, dy in dirs:
            nx, ny = x + dx, y + dy
            if not (0 <= nx < m and 0 <= ny < n):
                continue
            cell = maze[nx][ny]
            if cell == 1:
                continue  # obstacle
            new_s = s
            new_d = d
            if cell == 2:
                new_s += 1
                if new_s > 2:
                    continue
            if cell == 3:
                new_d += 1
            new_steps = steps + 1
            cur_best = best[nx][ny][new_s]
            if (new_d < cur_best[0]) or (new_d == cur_best[0] and new_steps < cur_best[1]):
                best[nx][ny][new_s] = (new_d, new_steps)
                heapq.heappush(heap, (new_d, new_steps, nx, ny, new_s))
    return "STUCK"

# Example usage
if __name__ == "__main__":
    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]
    print(constrained_maze_shortest_path(maze, start, target))
class State {
    constructor(d, steps, x, y, s) {
        this.d = d;
        this.steps = steps;
        this.x = x;
        this.y = y;
        this.s = s;
    }
}

function constrainedMazeShortestPath(maze, start, target) {
    const m = maze.length, n = maze[0].length;
    // best[x][y][s] = [minDangerous, minSteps]
    const best = Array.from({length: m}, () => 
        Array.from({length: n}, () => 
            Array(3).fill([Infinity, Infinity])
        )
    );
    const sx = start[0], sy = start[1];
    const tx = target[0], ty = target[1];
    best[sx][sy][0] = [0, 0];
    const heap = new State(0, 0, sx, sy, 0);
    const pq = [heap];
    const dirs = [[-1,0], [1,0], [0,-1], [0,1]];
    while (pq.length) {
        pq.sort((a,b) => a.d - b.d || a.steps - b.steps);
        const cur = pq.shift();
        const {x, y, s, d, steps} = cur;
        if (x === tx && y === ty) return steps;
        if (d > best[x][y][s][0] || (d === best[x][y][s][0] && steps > best[x][y][s][1])) continue;
        for (const [dx, dy] of dirs) {
            const nx = x + dx, ny = y + dy;
            if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
            const cell = maze[nx][ny];
            if (cell === 1) continue; // obstacle
            let new_s = s;
            let new_d = d;
            if (cell === 2) {
                new_s++;
                if (new_s > 2) continue;
            }
            if (cell === 3) new_d++;
            const new_steps = steps + 1;
            const cur_best = best[nx][ny][new_s];
            if (new_d < cur_best[0] || (new_d === cur_best[0] && new_steps < cur_best[1])) {
                best[nx][ny][new_s] = [new_d, new_steps];
                pq.push(new State(new_d, new_steps, nx, ny, new_s));
            }
        }
    }
    return "STUCK";
}

// Example usage
const 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]];
const start = [0,0];
const target = [4,4];
console.log(constrainedMazeShortestPath(maze, start, target));

Complexity Analysis:

Time Complexity: O(M * N * S * log(M * N * S)), where M and N are grid dimensions, S = 3 is the number of special-block states (0,1,2). Each cell can be processed up to 3 times (for each special count) and the priority queue operations dominate.

Space Complexity: O(M * N * S) for the best array and priority queue.

Notes

Your notes are automatically saved in your browser's local storage and will persist across sessions on this device.

Problem Categories