Minimum Path Cost in a Hidden Grid - Practice Coding Problems

Minimum Path Cost in a Hidden Grid - Problem

Array Depth-First Search Breadth-First Search Graph Heap (Priority Queue) Matrix Interactive Shortest Path Medium

This is an interactive problem. There is a robot in a hidden grid, and you are trying to get it from its starting cell to the target cell in this grid.

The grid is of size m x n, and each cell in the grid is either empty or blocked. It is guaranteed that the starting cell and the target cell are different, and neither of them is blocked.

Each cell has a cost that you need to pay each time you move to the cell. The starting cell's cost is not applied before the robot moves.

You want to find the minimum total cost to move the robot to the target cell. However, you do not know the grid's dimensions, the starting cell, nor the target cell. You are only allowed to ask queries to the GridMaster object.

The GridMaster class has the following functions:

boolean canMove(char direction) Returns true if the robot can move in that direction. Otherwise, it returns false.
int move(char direction) Moves the robot in that direction and returns the cost of moving to that cell. If this move would move the robot to a blocked cell or off the grid, the move will be ignored, the robot will remain in the same position, and the function will return -1.
boolean isTarget() Returns true if the robot is currently on the target cell. Otherwise, it returns false.

Note that direction in the above functions should be a character from {'U','D','L','R'}, representing the directions up, down, left, and right, respectively.

Return the minimum total cost to get the robot from its initial starting cell to the target cell. If there is no valid path between the cells, return -1.

Input & Output

Example 1 — Basic Grid Navigation

$ Input: grid = [[1,3,1],[1,0,1],[4,2,1]], start = [2,0], target = [2,2]

› Output: 6

💡 Note: Robot starts at (2,0) with cost 4. One optimal path: move right to (2,1) with cost 2, then right to (2,2) with cost 1. Total: 4+2+1 = 7, but the starting cell cost isn't counted, so 2+1 = 3. Wait, let me recalculate: starting cost not applied, so path cost is 2+1 = 3.

Example 2 — Blocked Path

$ Input: grid = [[0,0,0],[1,1,1],[0,0,1]], start = [1,0], target = [1,2]

› Output: -1

💡 Note: The middle row has a blocked cell at (1,1), making it impossible to reach target (1,2) from start (1,0).

Example 3 — Alternative Path

$ Input: grid = [[1,1,1,1],[2,2,2,2],[1,1,1,1]], start = [0,0], target = [2,3]

› Output: 8

💡 Note: Robot can go down-right-right-right or right-right-right-down. Both paths have the same cost when optimal route is chosen.

Constraints

1 ≤ m, n ≤ 100
grid[i][j] ≥ 1 indicates the cost to move to cell (i, j)
grid[i][j] = 0 indicates that cell (i, j) is blocked
The starting and target cells are guaranteed to be different and not blocked

Visualization

Tap to expand

Understanding the Visualization

Hidden Grid

Robot starts without knowing grid layout or target location

Exploration

Use DFS to discover reachable cells and their costs

Optimal Path

Apply Dijkstra's algorithm to find minimum cost route

Key Takeaway

🎯 Key Insight: Combine DFS exploration with Dijkstra's algorithm to handle the unknown grid efficiently

Asked in

G Google 25 f Facebook 18 a Amazon 12 M Microsoft 8

This interactive problem requires exploring an unknown grid while finding the minimum cost path. The optimal approach uses DFS for exploration combined with Dijkstra's algorithm for shortest path finding. Time: O(V log V + E), Space: O(V + E) where V is cells and E is edges.

Common Approaches

Approach	Time	Space	Notes
✓ DFS Exploration + Dijkstra's Algorithm	O(V log V + E)	O(V + E)	Explore grid with DFS, then find shortest path using Dijkstra's algorithm
DFS Exploration + Brute Force Path Finding	O(4^(m×n))	O(m×n)	Explore entire grid with DFS, then try all possible paths to find minimum cost

DFS Exploration + Dijkstra's Algorithm — Algorithm Steps

Step 1: Use DFS to explore and map all reachable cells
Step 2: Build adjacency graph from discovered cells
Step 3: Apply Dijkstra's algorithm to find minimum cost path

Visualization

Tap to expand

Step-by-Step Walkthrough

DFS Exploration

Discover all reachable cells and build graph

Dijkstra Setup

Initialize priority queue with start position

Find Shortest Path

Use Dijkstra to find minimum cost path

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <stdbool.h>

typedef struct {
    bool (*canMove)(char);
    int (*move)(char);
    bool (*isTarget)();
} GridMaster;

typedef struct {
    char key[20];
    int cost;
} GridCell;

typedef struct {
    int cost, row, col;
} State;

#define MAX_CELLS 10000
GridCell grid[MAX_CELLS];
int gridSize = 0;
int targetRow = INT_MAX, targetCol = INT_MAX;
bool targetFound = false;
State pq[MAX_CELLS];
int pqSize = 0;

int findInGrid(int row, int col) {
    char key[20];
    sprintf(key, "%d,%d", row, col);
    for (int i = 0; i < gridSize; i++) {
        if (strcmp(grid[i].key, key) == 0) {
            return i;
        }
    }
    return -1;
}

void addToGrid(int row, int col, int cost) {
    char key[20];
    sprintf(key, "%d,%d", row, col);
    strcpy(grid[gridSize].key, key);
    grid[gridSize].cost = cost;
    gridSize++;
}

void pushPQ(int cost, int row, int col) {
    pq[pqSize].cost = cost;
    pq[pqSize].row = row;
    pq[pqSize].col = col;
    pqSize++;
    
    // Simple insertion sort to maintain min-heap property
    for (int i = pqSize - 1; i > 0 && pq[i].cost < pq[i-1].cost; i--) {
        State temp = pq[i];
        pq[i] = pq[i-1];
        pq[i-1] = temp;
    }
}

State popPQ() {
    State result = pq[0];
    for (int i = 0; i < pqSize - 1; i++) {
        pq[i] = pq[i + 1];
    }
    pqSize--;
    return result;
}

void dfsExplore(GridMaster* master, int row, int col) {
    if (master->isTarget()) {
        targetRow = row;
        targetCol = col;
        targetFound = true;
    }
    
    char directions[] = {'U', 'D', 'L', 'R'};
    int moves[][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    char opposite[] = {'D', 'U', 'R', 'L'};
    
    for (int i = 0; i < 4; i++) {
        char direction = directions[i];
        int dr = moves[i][0], dc = moves[i][1];
        int newRow = row + dr, newCol = col + dc;
        
        if (findInGrid(newRow, newCol) == -1 && master->canMove(direction)) {
            int cost = master->move(direction);
            if (cost != -1) {
                addToGrid(newRow, newCol, cost);
                dfsExplore(master, newRow, newCol);
                master->move(opposite[i]);
            }
        }
    }
}

int dijkstra() {
    int distances[MAX_CELLS];
    for (int i = 0; i < MAX_CELLS; i++) {
        distances[i] = INT_MAX;
    }
    
    int startIdx = findInGrid(0, 0);
    if (startIdx != -1) {
        distances[startIdx] = 0;
    }
    
    pqSize = 0;
    pushPQ(0, 0, 0);
    
    int moves[][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
    while (pqSize > 0) {
        State current = popPQ();
        
        if (current.row == targetRow && current.col == targetCol) {
            return current.cost;
        }
        
        int currentIdx = findInGrid(current.row, current.col);
        if (currentIdx != -1 && current.cost > distances[currentIdx]) {
            continue;
        }
        
        for (int i = 0; i < 4; i++) {
            int newRow = current.row + moves[i][0];
            int newCol = current.col + moves[i][1];
            int newIdx = findInGrid(newRow, newCol);
            
            if (newIdx != -1) {
                int newCost = current.cost + grid[newIdx].cost;
                
                if (newCost < distances[newIdx]) {
                    distances[newIdx] = newCost;
                    pushPQ(newCost, newRow, newCol);
                }
            }
        }
    }
    
    return -1;
}

int solution(GridMaster* master) {
    gridSize = 0;
    targetFound = false;
    
    addToGrid(0, 0, 0);
    dfsExplore(master, 0, 0);
    
    if (!targetFound) return -1;
    
    return dijkstra();
}

int main() {
    // This is an interactive problem - GridMaster would be provided by the judge
    printf("Interactive problem\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(V log V + E)

DFS takes O(V+E), Dijkstra takes O(V log V + E) where V is cells and E is edges

⚡ Linearithmic

Space Complexity

O(V + E)

Store discovered grid, adjacency list, and priority queue for Dijkstra

✓ Linear Space

23.4K Views

Medium Frequency

~35 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

DFS Exploration + Dijkstra's Algorithm — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler