1810. Minimum Path Cost in a Hidden Grid π
Problem Description
This is an interactive problem where you need to guide a robot through a hidden grid from its starting position to a target cell with minimum total cost.
The grid has the following properties:
- Size is
m x n
(unknown to you) - Each cell is either empty (passable) or blocked
- Each empty cell has a cost that you pay when moving to it
- The starting cell and target cell are guaranteed to be different and not blocked
- The starting cell's cost is not counted
You interact with the grid through a GridMaster
object that provides three methods:
canMove(direction)
: Returnstrue
if the robot can move in the given direction ('U', 'D', 'L', 'R' for up, down, left, right)move(direction)
: Moves the robot in that direction and returns the cost of the new cell. Returns-1
if the move is invalid (blocked or out of bounds) and the robot stays in placeisTarget()
: Returnstrue
if the robot is currently at the target cell
Your task is to find the minimum total cost path from the starting position to the target cell. Return -1
if no valid path exists.
The challenge is that you don't know:
- The grid dimensions
- The starting position
- The target position
- The grid layout
You must explore the grid using the provided methods to discover the layout, find the target, and calculate the minimum cost path.
Flowchart Walkthrough
First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:
Is it a graph?
- Yes: The problem involves a grid where the robot moves between cells. A grid is a special type of graph where each cell is a node and adjacent cells are connected by edges.
Is it a tree?
- No: The grid structure is not a tree. It can have cycles (you can move in a square pattern and return to the same cell), and cells can have multiple paths between them.
Is the problem related to directed acyclic graphs?
- No: The grid allows bidirectional movement (if you can move from A to B, you can move back from B to A), and it contains cycles.
Is the problem related to shortest paths?
- Yes: The core objective is to find the minimum total cost path from the starting position to the target cell, which is a shortest path problem with weighted edges (each cell has a cost).
Is the graph weighted?
- Yes: Each cell has an associated cost that you must pay when moving to it. These costs act as edge weights in the graph representation.
Dijkstra's Algorithm
- The flowchart leads us to Dijkstra's Algorithm for finding the shortest path in a weighted graph.
Additional consideration for DFS: The solution actually uses DFS first for exploration phase. Since the grid is hidden and we need to discover it before finding the shortest path, DFS is used to:
- Explore the entire reachable grid from the starting position
- Build a map of the grid with cell costs
- Locate the target cell
After the DFS exploration phase completes, Dijkstra's algorithm (implemented using a priority queue) finds the minimum cost path from start to target.
Conclusion: The flowchart correctly identifies this as a weighted shortest path problem, suggesting Dijkstra's Algorithm. The solution combines DFS for grid exploration with Dijkstra's for finding the minimum cost path.
Intuition
The key insight is that we're dealing with a "hidden" grid - we can't see the entire map upfront, but we can explore it step by step. This is like being in a dark maze with a flashlight that only reveals adjacent rooms.
Since we don't know where the target is or what the grid looks like, we need to solve this problem in two phases:
Phase 1: Exploration (DFS) We need to map out the entire reachable grid first. DFS is perfect for this because:
- We can systematically explore every reachable cell from our starting position
- We need to backtrack to our current position after exploring each direction (DFS naturally handles this with recursion)
- As we explore, we record the cost of each cell we visit and check if we've found the target
Think of it like a scout exploring unknown territory - they venture out in one direction as far as possible, marking the terrain, then return to try another direction. The move()
and opposite move pattern (like moving 'U' then 'D') allows us to explore and return to our previous position.
Phase 2: Finding Minimum Cost Path (Dijkstra's) Once we have the complete map with all cell costs and know where the target is, finding the minimum cost path becomes a standard shortest path problem. We use Dijkstra's algorithm because:
- All costs are positive (as implied by the problem)
- We need the optimal (minimum cost) path, not just any path
- The grid we discovered in Phase 1 can now be treated as a weighted graph
The clever part is using a large fixed-size grid (200x200) with the robot starting at position (100, 100). This ensures we have enough space to explore in any direction without worrying about array boundaries. Cells we haven't visited remain marked as -1
, distinguishing them from valid cells.
If we never find the target during exploration, we return -1
. Otherwise, we run Dijkstra's algorithm on our discovered map to find the minimum cost from start to target.
Learn more about Depth-First Search, Breadth-First Search, Graph, Shortest Path and Heap (Priority Queue) patterns.
Solution Approach
The implementation follows the two-phase approach we identified:
Initial Setup:
- Create a 200x200 grid
g
initialized with-1
to represent unexplored cells - Start the robot at position (100, 100) in our internal representation (center of the grid to allow exploration in all directions)
- Define direction mappings with their opposites:
'U': (-1, 0, 'D')
,'D': (1, 0, 'U')
, etc. - Initialize
target
as(-1, -1)
to track if we find the target
Phase 1: DFS Exploration
def dfs(i, j):
if master.isTarget():
target = (i, j) # Record target position
for dir, (a, b, ndir) in dirs.items():
x, y = i + a, j + b
if master.canMove(dir) and g[x][y] == -1: # Can move and not visited
g[x][y] = master.move(dir) # Move and record cost
dfs(x, y) # Recursively explore
master.move(ndir) # Backtrack using opposite direction
The DFS function:
- Checks if current position is the target using
isTarget()
- For each direction, checks if movement is possible with
canMove()
- Only explores unvisited cells (
g[x][y] == -1
) - Records the cost returned by
move()
in the grid - Recursively explores from the new position
- Backtracks by moving in the opposite direction (
ndir
)
Phase 2: Dijkstra's Algorithm
After exploration, if no target was found (target == (-1, -1)
), return -1
.
Otherwise, use Dijkstra's algorithm with a min-heap:
q = [(0, 100, 100)] # (cost, row, col) - start with 0 cost at starting position
dist = [[INF] * N for _ in range(N)] # Distance array
dist[100][100] = 0
The algorithm proceeds as:
- Pop the cell with minimum cost from the heap
- If it's the target, return the cost
- For each adjacent cell that was discovered during DFS (
g[x][y] != -1
):- Calculate new cost:
current_cost + g[x][y]
- If this cost is better than the recorded distance, update it
- Push the new state
(new_cost, x, y)
to the heap
- Calculate new cost:
Key Data Structures:
- 2D Grid
g
: Stores the cost of each discovered cell,-1
for unexplored - Min-Heap
q
: Priority queue for Dijkstra's algorithm, ordered by cumulative cost - 2D Distance Array
dist
: Tracks minimum cost to reach each cell - Direction Dictionary
dirs
: Maps each direction to its movement delta and opposite direction
The solution elegantly handles the unknown grid size by using a large fixed grid and starting from the center, ensuring enough space for exploration in any direction. The combination of DFS for discovery and Dijkstra's for pathfinding provides an optimal solution to this interactive problem.
Ready to land your dream job?
Unlock your dream job with a 3-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small hidden grid example to illustrate the solution approach.
Hidden Grid (unknown to us initially):
[1] [2] [#] [3] [T] [5] [S] [4] [6]
Where S = Start, T = Target (cost 4), # = Blocked cell
Phase 1: DFS Exploration
Starting at position (100, 100) in our internal grid:
- Initial state: Robot at S,
g[100][100] = 0
(starting cell) - Check
isTarget()
: Returnsfalse
- Try moving Up:
canMove('U')
returnstrue
move('U')
returns cost 3, robot now at cell with cost 3- Record
g[99][100] = 3
- Recursively explore from (99, 100)
- From (99, 100), try all directions:
- Up:
canMove('U')
returnstrue
,move('U')
returns 1, recordg[98][100] = 1
- From (98, 100): Can't move Up (out of bounds), Left returns 2, Right is blocked
- Backtrack to (99, 100) with
move('D')
- Right:
canMove('R')
returnstrue
,move('R')
returns 4,isTarget()
returnstrue
! - Record
target = (99, 101)
andg[99][101] = 4
- Continue exploring to map remaining cells
- Up:
- Continue DFS until all reachable cells are explored
Discovered Grid (in our internal representation):
g[98][99]=2 g[98][100]=1 g[98][101]=-1 (blocked) g[99][99]=3 g[99][100]=3 g[99][101]=4 (target) g[100][99]=0 g[100][100]=0 g[100][101]=4 (start) g[101][101]=6
Phase 2: Dijkstra's Algorithm
Now we find the minimum cost path from (100, 100) to target (99, 101):
-
Initialize:
- Min-heap:
[(0, 100, 100)]
dist[100][100] = 0
- Min-heap:
-
Process (100, 100) with cost 0:
- Check neighbors:
- Up (99, 100): cost = 0 + 3 = 3, update
dist[99][100] = 3
, push(3, 99, 100)
- Right (100, 101): cost = 0 + 4 = 4, update
dist[100][101] = 4
, push(4, 100, 101)
- Up (99, 100): cost = 0 + 3 = 3, update
- Check neighbors:
-
Process (99, 100) with cost 3:
- Check neighbors:
- Up (98, 100): cost = 3 + 1 = 4, update
dist[98][100] = 4
, push(4, 98, 100)
- Left (99, 99): cost = 3 + 3 = 6, update
dist[99][99] = 6
, push(6, 99, 99)
- Right (99, 101): cost = 3 + 4 = 7, update
dist[99][101] = 7
, push(7, 99, 101)
- Up (98, 100): cost = 3 + 1 = 4, update
- Check neighbors:
-
Process (100, 101) with cost 4:
- Check neighbors:
- Up (99, 101): cost = 4 + 4 = 8, but
dist[99][101] = 7
(already better) - Down (101, 101): cost = 4 + 6 = 10
- Up (99, 101): cost = 4 + 4 = 8, but
- Check neighbors:
-
Process (98, 100) with cost 4:
- Continue exploring...
-
Process (99, 101) with cost 7:
- This is our target! Return cost = 7
Result: Minimum cost path is S β (cost 3) β (cost 4) = total cost 7
The optimal path goes from Start up to the cell with cost 3, then right to the Target with cost 4, giving us a total cost of 3 + 4 = 7.
Solution Implementation
1from heapq import heappush, heappop
2from typing import Optional
3
4class Solution:
5 def findShortestPath(self, master: 'GridMaster') -> int:
6 """
7 Find the shortest path from starting position to target in a hidden grid.
8
9 Strategy:
10 1. First, explore the entire reachable grid using DFS to build a map
11 2. Then use Dijkstra's algorithm to find the shortest path to target
12
13 Returns:
14 The minimum cost to reach target, or -1 if target is unreachable
15 """
16
17 def explore_grid(row: int, col: int) -> None:
18 """
19 DFS to explore the grid and record cell costs and target location.
20
21 Args:
22 row: Current row position
23 col: Current column position
24 """
25 nonlocal target_position
26
27 # Check if current position is the target
28 if master.isTarget():
29 target_position = (row, col)
30
31 # Try moving in all four directions
32 for direction, (row_delta, col_delta, opposite_dir) in directions.items():
33 next_row = row + row_delta
34 next_col = col + col_delta
35
36 # Check boundaries and if we can move to this cell
37 if (0 <= next_row < GRID_SIZE and
38 0 <= next_col < GRID_SIZE and
39 master.canMove(direction) and
40 grid[next_row][next_col] == -1):
41
42 # Move to the cell and record its cost
43 grid[next_row][next_col] = master.move(direction)
44
45 # Recursively explore from the new position
46 explore_grid(next_row, next_col)
47
48 # Backtrack to original position
49 master.move(opposite_dir)
50
51 # Initialize constants and data structures
52 target_position = (-1, -1) # Target coordinates, (-1, -1) if not found
53 GRID_SIZE = 200 # Maximum grid size (using center as starting point)
54 INFINITY = 0x3F3F3F3F # Large value representing infinity
55 START_POS = 100 # Starting position in the grid (center)
56
57 # Initialize grid with -1 (unexplored cells)
58 grid = [[-1] * GRID_SIZE for _ in range(GRID_SIZE)]
59
60 # Direction mappings: direction -> (row_delta, col_delta, opposite_direction)
61 directions = {
62 'U': (-1, 0, 'D'), # Up
63 'D': (1, 0, 'U'), # Down
64 'L': (0, -1, 'R'), # Left
65 'R': (0, 1, 'L'), # Right
66 }
67
68 # Phase 1: Explore the grid using DFS from starting position
69 explore_grid(START_POS, START_POS)
70
71 # If target was not found during exploration, return -1
72 if target_position == (-1, -1):
73 return -1
74
75 # Phase 2: Find shortest path using Dijkstra's algorithm
76 # Priority queue: (cost, row, col)
77 priority_queue = [(0, START_POS, START_POS)]
78
79 # Distance matrix to track minimum cost to reach each cell
80 distance = [[INFINITY] * GRID_SIZE for _ in range(GRID_SIZE)]
81 distance[START_POS][START_POS] = 0
82
83 while priority_queue:
84 current_cost, current_row, current_col = heappop(priority_queue)
85
86 # If we reached the target, return the cost
87 if (current_row, current_col) == target_position:
88 return current_cost
89
90 # Check all adjacent cells
91 for row_delta, col_delta, _ in directions.values():
92 next_row = current_row + row_delta
93 next_col = current_col + col_delta
94
95 # Check if the next cell is valid and can improve the path
96 if (0 <= next_row < GRID_SIZE and
97 0 <= next_col < GRID_SIZE and
98 grid[next_row][next_col] != -1): # Cell has been explored
99
100 new_cost = current_cost + grid[next_row][next_col]
101
102 # If we found a shorter path to this cell, update it
103 if distance[next_row][next_col] > new_cost:
104 distance[next_row][next_col] = new_cost
105 heappush(priority_queue, (new_cost, next_row, next_col))
106
107 # Target is unreachable (shouldn't happen if exploration found it)
108 return 0
109
1/**
2 * // This is the GridMaster's API interface.
3 * // You should not implement it, or speculate about its implementation
4 * class GridMaster {
5 * boolean canMove(char direction);
6 * int move(char direction);
7 * boolean isTarget();
8 * }
9 */
10
11class Solution {
12 // Direction arrays for movement: Up, Right, Down, Left
13 private static final char[] DIRECTIONS = {'U', 'R', 'D', 'L'};
14 private static final char[] OPPOSITE_DIRECTIONS = {'D', 'L', 'U', 'R'};
15 // Direction deltas: (row, col) changes for Up, Right, Down, Left
16 private static final int[] DIRECTION_DELTAS = {-1, 0, 1, 0, -1};
17
18 // Grid dimensions and constants
19 private static final int GRID_SIZE = 200;
20 private static final int INFINITY = 0x3f3f3f3f;
21
22 // Grid to store cell costs (-1 means unvisited/blocked)
23 private static int[][] grid = new int[GRID_SIZE][GRID_SIZE];
24 // Distance array for Dijkstra's algorithm
25 private static int[][] distance = new int[GRID_SIZE][GRID_SIZE];
26
27 // Target cell coordinates
28 private int[] targetPosition;
29
30 public int findShortestPath(GridMaster master) {
31 // Initialize target position as not found
32 targetPosition = new int[] {-1, -1};
33
34 // Initialize grid and distance arrays
35 for (int row = 0; row < GRID_SIZE; row++) {
36 Arrays.fill(grid[row], -1);
37 Arrays.fill(distance[row], INFINITY);
38 }
39
40 // Explore the grid starting from center position (100, 100)
41 exploreMaze(100, 100, master);
42
43 // If target was not found during exploration, return -1
44 if (targetPosition[0] == -1 && targetPosition[1] == -1) {
45 return -1;
46 }
47
48 // Run Dijkstra's algorithm to find shortest path
49 // Priority queue stores: [distance, row, col]
50 PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(
51 Comparator.comparingInt(a -> a[0])
52 );
53
54 // Start from center position with distance 0
55 priorityQueue.offer(new int[] {0, 100, 100});
56 distance[100][100] = 0;
57
58 // Process nodes in order of increasing distance
59 while (!priorityQueue.isEmpty()) {
60 int[] current = priorityQueue.poll();
61 int currentDistance = current[0];
62 int currentRow = current[1];
63 int currentCol = current[2];
64
65 // Check if we reached the target
66 if (currentRow == targetPosition[0] && currentCol == targetPosition[1]) {
67 return currentDistance;
68 }
69
70 // Explore all four directions
71 for (int direction = 0; direction < 4; direction++) {
72 int nextRow = currentRow + DIRECTION_DELTAS[direction];
73 int nextCol = currentCol + DIRECTION_DELTAS[direction + 1];
74
75 // Check if next position is valid and can improve distance
76 if (nextRow >= 0 && nextRow < GRID_SIZE &&
77 nextCol >= 0 && nextCol < GRID_SIZE &&
78 grid[nextRow][nextCol] != -1) {
79
80 int newDistance = currentDistance + grid[nextRow][nextCol];
81 if (distance[nextRow][nextCol] > newDistance) {
82 distance[nextRow][nextCol] = newDistance;
83 priorityQueue.offer(new int[] {newDistance, nextRow, nextCol});
84 }
85 }
86 }
87 }
88
89 // Should not reach here if target was found during exploration
90 return 0;
91 }
92
93 /**
94 * Recursively explore the maze using DFS and build the grid representation
95 * @param row Current row position
96 * @param col Current column position
97 * @param master GridMaster API to interact with the maze
98 */
99 private void exploreMaze(int row, int col, GridMaster master) {
100 // Check if current position is the target
101 if (master.isTarget()) {
102 targetPosition = new int[] {row, col};
103 }
104
105 // Try moving in all four directions
106 for (int directionIndex = 0; directionIndex < 4; directionIndex++) {
107 char moveDirection = DIRECTIONS[directionIndex];
108 char returnDirection = OPPOSITE_DIRECTIONS[directionIndex];
109 int nextRow = row + DIRECTION_DELTAS[directionIndex];
110 int nextCol = col + DIRECTION_DELTAS[directionIndex + 1];
111
112 // Check if we can move in this direction and haven't visited this cell yet
113 if (nextRow >= 0 && nextRow < GRID_SIZE &&
114 nextCol >= 0 && nextCol < GRID_SIZE &&
115 master.canMove(moveDirection) &&
116 grid[nextRow][nextCol] == -1) {
117
118 // Move to the next cell and record its cost
119 grid[nextRow][nextCol] = master.move(moveDirection);
120
121 // Recursively explore from the new position
122 exploreMaze(nextRow, nextCol, master);
123
124 // Backtrack to the original position
125 master.move(returnDirection);
126 }
127 }
128 }
129}
130
1/**
2 * // This is the GridMaster's API interface.
3 * // You should not implement it, or speculate about its implementation
4 * class GridMaster {
5 * public:
6 * bool canMove(char direction);
7 * int move(char direction);
8 * bool isTarget();
9 * };
10 */
11
12class Solution {
13private:
14 // Direction arrays for movement: Up, Right, Down, Left
15 static constexpr char DIRECTIONS[4] = {'U', 'R', 'D', 'L'};
16 static constexpr char OPPOSITE_DIRECTIONS[4] = {'D', 'L', 'U', 'R'};
17 // Direction deltas: (row, col) changes for Up, Right, Down, Left
18 static constexpr int DIRECTION_DELTAS[5] = {-1, 0, 1, 0, -1};
19
20 // Grid dimensions and constants
21 static constexpr int GRID_SIZE = 200;
22 static constexpr int INFINITY = 0x3f3f3f3f;
23
24 // Grid to store cell costs (-1 means unvisited/blocked)
25 int grid[GRID_SIZE][GRID_SIZE];
26 // Distance array for Dijkstra's algorithm
27 int distance[GRID_SIZE][GRID_SIZE];
28
29 // Target cell coordinates
30 int targetRow;
31 int targetCol;
32
33public:
34 int findShortestPath(GridMaster* master) {
35 // Initialize target position as not found
36 targetRow = -1;
37 targetCol = -1;
38
39 // Initialize grid and distance arrays
40 for (int row = 0; row < GRID_SIZE; row++) {
41 for (int col = 0; col < GRID_SIZE; col++) {
42 grid[row][col] = -1;
43 distance[row][col] = INFINITY;
44 }
45 }
46
47 // Explore the grid starting from center position (100, 100)
48 exploreMaze(100, 100, master);
49
50 // If target was not found during exploration, return -1
51 if (targetRow == -1 && targetCol == -1) {
52 return -1;
53 }
54
55 // Run Dijkstra's algorithm to find shortest path
56 // Priority queue stores: {distance, row, col}
57 priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> pq;
58
59 // Start from center position with distance 0
60 pq.push({0, 100, 100});
61 distance[100][100] = 0;
62
63 // Process nodes in order of increasing distance
64 while (!pq.empty()) {
65 vector<int> current = pq.top();
66 pq.pop();
67
68 int currentDistance = current[0];
69 int currentRow = current[1];
70 int currentCol = current[2];
71
72 // Check if we reached the target
73 if (currentRow == targetRow && currentCol == targetCol) {
74 return currentDistance;
75 }
76
77 // Skip if we've already found a better path to this node
78 if (currentDistance > distance[currentRow][currentCol]) {
79 continue;
80 }
81
82 // Explore all four directions
83 for (int direction = 0; direction < 4; direction++) {
84 int nextRow = currentRow + DIRECTION_DELTAS[direction];
85 int nextCol = currentCol + DIRECTION_DELTAS[direction + 1];
86
87 // Check if next position is valid and can improve distance
88 if (nextRow >= 0 && nextRow < GRID_SIZE &&
89 nextCol >= 0 && nextCol < GRID_SIZE &&
90 grid[nextRow][nextCol] != -1) {
91
92 int newDistance = currentDistance + grid[nextRow][nextCol];
93 if (distance[nextRow][nextCol] > newDistance) {
94 distance[nextRow][nextCol] = newDistance;
95 pq.push({newDistance, nextRow, nextCol});
96 }
97 }
98 }
99 }
100
101 // Should not reach here if target was found during exploration
102 return -1;
103 }
104
105private:
106 /**
107 * Recursively explore the maze using DFS and build the grid representation
108 * @param row Current row position
109 * @param col Current column position
110 * @param master GridMaster API to interact with the maze
111 */
112 void exploreMaze(int row, int col, GridMaster* master) {
113 // Check if current position is the target
114 if (master->isTarget()) {
115 targetRow = row;
116 targetCol = col;
117 }
118
119 // Try moving in all four directions
120 for (int directionIndex = 0; directionIndex < 4; directionIndex++) {
121 char moveDirection = DIRECTIONS[directionIndex];
122 char returnDirection = OPPOSITE_DIRECTIONS[directionIndex];
123 int nextRow = row + DIRECTION_DELTAS[directionIndex];
124 int nextCol = col + DIRECTION_DELTAS[directionIndex + 1];
125
126 // Check if we can move in this direction and haven't visited this cell yet
127 if (nextRow >= 0 && nextRow < GRID_SIZE &&
128 nextCol >= 0 && nextCol < GRID_SIZE &&
129 master->canMove(moveDirection) &&
130 grid[nextRow][nextCol] == -1) {
131
132 // Move to the next cell and record its cost
133 grid[nextRow][nextCol] = master->move(moveDirection);
134
135 // Recursively explore from the new position
136 exploreMaze(nextRow, nextCol, master);
137
138 // Backtrack to the original position
139 master->move(returnDirection);
140 }
141 }
142 }
143};
144
1/**
2 * // This is the GridMaster's API interface.
3 * // You should not implement it, or speculate about its implementation
4 * class GridMaster {
5 * boolean canMove(char direction);
6 * int move(char direction);
7 * boolean isTarget();
8 * }
9 */
10
11// Direction arrays for movement: Up, Right, Down, Left
12const DIRECTIONS: string[] = ['U', 'R', 'D', 'L'];
13const OPPOSITE_DIRECTIONS: string[] = ['D', 'L', 'U', 'R'];
14
15// Direction deltas: (row, col) changes for Up, Right, Down, Left
16const DIRECTION_DELTAS: number[] = [-1, 0, 1, 0, -1];
17
18// Grid dimensions and constants
19const GRID_SIZE: number = 200;
20const INFINITY: number = 0x3f3f3f3f;
21
22// Grid to store cell costs (-1 means unvisited/blocked)
23let grid: number[][] = [];
24
25// Distance array for Dijkstra's algorithm
26let distance: number[][] = [];
27
28// Target cell coordinates
29let targetPosition: number[] = [];
30
31/**
32 * Find the shortest path from start to target in the maze
33 * @param master - GridMaster API to interact with the maze
34 * @returns The minimum cost to reach the target, or -1 if unreachable
35 */
36function findShortestPath(master: GridMaster): number {
37 // Initialize target position as not found
38 targetPosition = [-1, -1];
39
40 // Initialize grid and distance arrays
41 grid = Array(GRID_SIZE).fill(null).map(() => Array(GRID_SIZE).fill(-1));
42 distance = Array(GRID_SIZE).fill(null).map(() => Array(GRID_SIZE).fill(INFINITY));
43
44 // Explore the grid starting from center position (100, 100)
45 exploreMaze(100, 100, master);
46
47 // If target was not found during exploration, return -1
48 if (targetPosition[0] === -1 && targetPosition[1] === -1) {
49 return -1;
50 }
51
52 // Run Dijkstra's algorithm to find shortest path
53 // Priority queue stores: [distance, row, col]
54 const priorityQueue: number[][] = [];
55
56 // Start from center position with distance 0
57 priorityQueue.push([0, 100, 100]);
58 distance[100][100] = 0;
59
60 // Process nodes in order of increasing distance
61 while (priorityQueue.length > 0) {
62 // Sort by distance to simulate priority queue behavior
63 priorityQueue.sort((a, b) => a[0] - b[0]);
64
65 const current = priorityQueue.shift()!;
66 const currentDistance = current[0];
67 const currentRow = current[1];
68 const currentCol = current[2];
69
70 // Check if we reached the target
71 if (currentRow === targetPosition[0] && currentCol === targetPosition[1]) {
72 return currentDistance;
73 }
74
75 // Explore all four directions
76 for (let direction = 0; direction < 4; direction++) {
77 const nextRow = currentRow + DIRECTION_DELTAS[direction];
78 const nextCol = currentCol + DIRECTION_DELTAS[direction + 1];
79
80 // Check if next position is valid and can improve distance
81 if (nextRow >= 0 && nextRow < GRID_SIZE &&
82 nextCol >= 0 && nextCol < GRID_SIZE &&
83 grid[nextRow][nextCol] !== -1) {
84
85 const newDistance = currentDistance + grid[nextRow][nextCol];
86 if (distance[nextRow][nextCol] > newDistance) {
87 distance[nextRow][nextCol] = newDistance;
88 priorityQueue.push([newDistance, nextRow, nextCol]);
89 }
90 }
91 }
92 }
93
94 // Should not reach here if target was found during exploration
95 return 0;
96}
97
98/**
99 * Recursively explore the maze using DFS and build the grid representation
100 * @param row - Current row position
101 * @param col - Current column position
102 * @param master - GridMaster API to interact with the maze
103 */
104function exploreMaze(row: number, col: number, master: GridMaster): void {
105 // Check if current position is the target
106 if (master.isTarget()) {
107 targetPosition = [row, col];
108 }
109
110 // Try moving in all four directions
111 for (let directionIndex = 0; directionIndex < 4; directionIndex++) {
112 const moveDirection = DIRECTIONS[directionIndex];
113 const returnDirection = OPPOSITE_DIRECTIONS[directionIndex];
114 const nextRow = row + DIRECTION_DELTAS[directionIndex];
115 const nextCol = col + DIRECTION_DELTAS[directionIndex + 1];
116
117 // Check if we can move in this direction and haven't visited this cell yet
118 if (nextRow >= 0 && nextRow < GRID_SIZE &&
119 nextCol >= 0 && nextCol < GRID_SIZE &&
120 master.canMove(moveDirection) &&
121 grid[nextRow][nextCol] === -1) {
122
123 // Move to the next cell and record its cost
124 grid[nextRow][nextCol] = master.move(moveDirection);
125
126 // Recursively explore from the new position
127 exploreMaze(nextRow, nextCol, master);
128
129 // Backtrack to the original position
130 master.move(returnDirection);
131 }
132 }
133}
134
Time and Space Complexity
Time Complexity: O(NΒ²)
The algorithm consists of two main phases:
-
DFS Exploration Phase: The DFS explores the reachable cells in the grid. In the worst case, all
NΓN
cells could be reachable. For each cell, we check 4 directions and potentially make recursive calls. Since each cell is visited at most once (marked byg[x][y] != -1
), the DFS runs inO(NΒ²)
time. -
Dijkstra's Shortest Path Phase: We use a min-heap based Dijkstra's algorithm to find the shortest path from the starting position to the target. In the worst case:
- We process up to
NΒ²
vertices (cells) - Each vertex can be pushed to the heap at most once per relaxation
- Each heap operation (push/pop) takes
O(log(NΒ²)) = O(log N)
- For each vertex, we check 4 neighbors
Total:
O(NΒ² Γ log N)
for Dijkstra's algorithm. - We process up to
Since N = 200
is a constant in this implementation, and O(NΒ² Γ log N)
dominates O(NΒ²)
, the overall time complexity is O(NΒ² Γ log N)
. However, treating N
as the actual grid dimension that could be explored, the complexity simplifies to O(NΒ²)
when considering that the log factor is relatively small.
Space Complexity: O(NΒ²)
The space usage includes:
g
matrix:N Γ N
grid storing cell costs =O(NΒ²)
dist
matrix:N Γ N
grid storing distances =O(NΒ²)
- Recursion stack for DFS: maximum depth is
O(NΒ²)
in worst case - Priority queue: can contain at most
O(NΒ²)
elements
Total space complexity is O(NΒ²)
.
Learn more about how to find time and space complexity quickly.
Common Pitfalls
1. Forgetting to Mark the Starting Cell as Explored
One of the most common mistakes is not properly initializing the starting cell in the grid. The starting cell should be marked as explored with cost 0, but developers often forget this crucial step.
The Problem:
# WRONG: Starting cell remains -1 (unexplored)
grid = [[-1] * GRID_SIZE for _ in range(GRID_SIZE)]
explore_grid(START_POS, START_POS)
Without marking the starting cell, Dijkstra's algorithm may treat it as unexplored and fail to properly calculate paths.
The Solution:
# CORRECT: Mark starting cell as explored with cost 0
grid = [[-1] * GRID_SIZE for _ in range(GRID_SIZE)]
grid[START_POS][START_POS] = 0 # Starting cell has cost 0
explore_grid(START_POS, START_POS)
2. Incorrect Handling of Target Position Scope
Using target_position
as a local variable in the DFS function instead of properly updating the outer scope variable.
The Problem:
def explore_grid(row, col):
if master.isTarget():
target_position = (row, col) # Creates local variable, doesn't update outer scope!
The Solution:
def explore_grid(row, col):
nonlocal target_position # Declare we're modifying the outer scope variable
if master.isTarget():
target_position = (row, col)
3. Not Checking if Cell Was Already Visited in DFS
Exploring the same cell multiple times can lead to infinite recursion or incorrect cost recording.
The Problem:
# WRONG: Moving without checking if cell was already explored if master.canMove(direction): # Missing check for grid[next_row][next_col] == -1 grid[next_row][next_col] = master.move(direction) explore_grid(next_row, next_col)
The Solution:
# CORRECT: Only explore unvisited cells if master.canMove(direction) and grid[next_row][next_col] == -1: grid[next_row][next_col] = master.move(direction) explore_grid(next_row, next_col)
4. Using Wrong Cost in Dijkstra's Algorithm
A critical mistake is using the visited check (distance[next_row][next_col] == INFINITY
) instead of properly comparing costs for relaxation.
The Problem:
# WRONG: Only checking if unvisited, not if we found a better path if distance[next_row][next_col] == INFINITY: distance[next_row][next_col] = new_cost heappush(priority_queue, (new_cost, next_row, next_col))
The Solution:
# CORRECT: Update if we found a shorter path if distance[next_row][next_col] > new_cost: distance[next_row][next_col] = new_cost heappush(priority_queue, (new_cost, next_row, next_col))
5. Grid Size Too Small for Large Mazes
Using a grid that's too small might cause index out of bounds errors during exploration.
The Problem:
GRID_SIZE = 50 # Too small for potentially large grids START_POS = 25 # Not enough room to explore in all directions
The Solution:
GRID_SIZE = 200 # Large enough for most practical cases START_POS = 100 # Center position allows exploration in all directions
What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)
Recommended Readings
https assets algo monster cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS As the name suggests
https assets algo monster cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell Breadth First Search BFS
https assets algo monster cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could be disconnected A tree
Want a Structured Path to Master System Design Too? Donβt Miss This!