Leetcode 1810. Minimum Path Cost in a Hidden Grid Solution
Problem Explanation
In this problem, there is a robot located in a hidden grid, and our task is to find the minimum total cost to move the robot from its initial starting cell to the target cell. The grid is of size n x m. Each cell has a cost that needs to be paid each time the robot moves to the cell. The cost of the starting cell is not applied before the robot moves. We do not know the dimensions of the grid, the starting cell, or the target cell. However, we are allowed to ask queries to the GridMaster object which has three functions - canMove(char direction), move(char direction), and isTarget(). The task is to return the minimum total cost to get the robot to the target cell, or return -1 if there is no valid path between the cells.
Let's walkthrough an example to understand the problem:
Example
1grid = [[2,3],[1,1]] 2r1 = 0 3c1 = 1 4r2 = 1 5c2 = 0
The robot is initially at the cell (0, 1). The grid looks like this:
12 3 21 1
To solve the problem, we will use DFS (Depth First Search) to build the grid information, and use BFS (Breadth First Search) with a priority queue (min heap) to find the minimum cost.
Approach
- Initialize grid, startX, startY, target and seen matrix.
- Build the grid information using DFS by querying the GridMaster object.
- Perform BFS using a priority queue (min heap) to find the minimum cost from starting position to target position.
- Return the minimum cost or -1 if there is no valid path between the cells.
Now let's walk through the algorithm using the example above.
Walkthrough
- Initialize grid, startX, startY, target and seen matrix.
1grid = [ 2[-1, -1, -1, ..., -1], 3[-1, -1, -1, ..., -1], 4... 5] 6startX = 100 7startY = 100 8target = [200, 200] 9seen = [ 10[False, False, False, ..., False], 11[False, False, False, ..., False], 12... 13] 14
- Perform DFS starting from (startX, startY):
1DFS(100, 100, grid, seen): 2 - The robot is initially at (100, 100) of the grid. 3 - The robot can move in 'D' and 'L' directions. 4 - Lower the cost of moving to (100, 101) which costs 3 and (100, 99) which costs 2. 5 - Move the robot to (100, 99), perform DFS on (100, 99): 6 DFS(100, 99, grid, seen): 7 - The robot can move in 'D' and 'R' directions. 8 - Move the robot to (101, 99), perform DFS on (101, 99): 9 DFS(101, 99, grid, seen): 10 - The robot is now at the target cell. 11 - Update target to [101, 99] 12 - Return 13 - Move the robot back to the initial position.
At this stage, the grid and target have been updated as follows:
1grid = [ 2 ... 3 [-1, ..., 2, 3, ...], 4 [-1, ..., 1, 1, ...], 5 ... 6] 7target = [101, 99]
- Perform BFS using a priority queue (min heap) to find the minimum cost.
- Add the initial position (100, 100) with cost 0 to the min heap.
- Iterate through the queue until it is empty:
- Pop the cell with the smallest cost.
- Check if that cell is the target cell.
- If yes, return the cost.
- Otherwise, check the adjacent cells and push the cell with valid moves and their cost to the min heap.
- When the min heap is empty, the loop ends, and no valid path is found, return -1.
In this specific case, the minimum total cost of moving the robot from its initial starting cell to the target cell is 2.
Python Solution
1from heapq import heappush, heappop
2
3class Solution:
4 def findShortestPath(self, master: 'GridMaster') -> int:
5 m = 100
6 startX, startY = m, m
7 target = [m * 2, m * 2]
8 grid = [[-1] * (m * 2) for _ in range(m * 2)]
9 seen = [[False] * (m * 2) for _ in range(m * 2)]
10
11 dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
12 charTable = ['R', 'D', 'L', 'U']
13
14 def dfs(master, i, j):
15 if master.isTarget():
16 target[0], target[1] = i, j
17
18 for k in range(4):
19 x, y = i + dirs[k][0], j + dirs[k][1]
20 d, undoD = charTable[k], charTable[(k + 2) % 4]
21 if master.canMove(d) and grid[x][y] == -1:
22 grid[x][y] = master.move(d)
23 dfs(master, x, y)
24 master.move(undoD)
25
26 dfs(master, startX, startY)
27
28 minHeap = []
29
30 heappush(minHeap, (0, startX, startY))
31
32 while minHeap:
33 cost, i, j = heappop(minHeap)
34 if i == target[0] and j == target[1]:
35 return cost
36 if seen[i][j]:
37 continue
38 seen[i][j] = True
39 for k in range(4):
40 x, y = i + dirs[k][0], j + dirs[k][1]
41 if 0 <= x < m * 2 and 0 <= y < m * 2 and not seen[x][y] and grid[x][y] != -1:
42 nextCost = cost + grid[x][y]
43 heappush(minHeap, (nextCost, x, y))
44
45 return -1
46
The solution follows the discussed approach. The DFS function is used to build the grid. The BFS is performed using a priority queue (min heap) to find the minimum cost. Finally, return the minimum cost or -1 if no valid path is found.## JavaScript Solution
1class Solution {
2 findShortestPath(master) {
3 const m = 100;
4 const startX = m, startY = m;
5 const target = [m * 2, m * 2];
6 const grid = new Array(m * 2).fill(null).map(() => new Array(m * 2).fill(-1));
7 const seen = new Array(m * 2).fill(null).map(() => new Array(m * 2).fill(false));
8 const dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]];
9 const charTable = ['R', 'D', 'L', 'U'];
10
11 function dfs(master, i, j) {
12 if (master.isTarget()) {
13 target[0] = i;
14 target[1] = j;
15 }
16
17 for (let k = 0; k < 4; k++) {
18 const x = i + dirs[k][0];
19 const y = j + dirs[k][1];
20 const d = charTable[k];
21 const undoD = charTable[(k + 2) % 4];
22 if (master.canMove(d) && grid[x][y] === -1) {
23 grid[x][y] = master.move(d);
24 dfs(master, x, y);
25 master.move(undoD);
26 }
27 }
28 }
29
30 dfs(master, startX, startY);
31
32 const minHeap = [];
33
34 minHeap.push([0, startX, startY]);
35
36 while (minHeap.length) {
37 const [cost, i, j] = minHeap.shift();
38 if (i === target[0] && j === target[1]) {
39 return cost;
40 }
41 if (seen[i][j]) {
42 continue;
43 }
44 seen[i][j] = true;
45 for (let k = 0; k < 4; k++) {
46 const x = i + dirs[k][0];
47 const y = j + dirs[k][1];
48 if (x >= 0 && x < m * 2 && y >= 0 && y < m * 2 && !seen[x][y] && grid[x][y] !== -1) {
49 const nextCost = cost + grid[x][y];
50 minHeap.push([nextCost, x, y]);
51 }
52 }
53 }
54
55 return -1;
56 }
57}
The JavaScript solution has the same structure as the Python solution. It first performs DFS to build the grid, and then BFS using a priority queue (an array - minHeap) to find the minimum cost. Finally, it returns the minimum cost, or -1 if no valid path is found.
Java Solution
1class Solution {
2 public int findShortestPath(GridMaster master) {
3 int m = 100;
4 int startX = m, startY = m;
5 int[] target = new int[]{m * 2, m * 2};
6 int[][] grid = new int[m * 2][m * 2];
7 boolean[][] seen = new boolean[m * 2][m * 2];
8 int[][] dirs = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
9 char[] charTable = new char[]{'R', 'D', 'L', 'U'};
10
11 for (int i = 0; i < m * 2; i++) {
12 Arrays.fill(grid[i], -1);
13 }
14
15 dfs(master, startX, startY, grid, seen, dirs, charTable, target);
16
17 PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
18
19 minHeap.offer(new int[]{0, startX, startY});
20
21 while (!minHeap.isEmpty()) {
22 int[] curr = minHeap.poll();
23 int cost = curr[0];
24 int i = curr[1];
25 int j = curr[2];
26
27 if (i == target[0] && j == target[1]) {
28 return cost;
29 }
30 if (seen[i][j]) {
31 continue;
32 }
33 seen[i][j] = true;
34 for (int k = 0; k < 4; k++) {
35 int x = i + dirs[k][0];
36 int y = j + dirs[k][1];
37 if (x >= 0 && x < m * 2 && y >= 0 && y < m * 2 && !seen[x][y] && grid[x][y] != -1) {
38 int nextCost = cost + grid[x][y];
39 minHeap.offer(new int[]{nextCost, x, y});
40 }
41 }
42 }
43
44 return -1;
45 }
46
47 private void dfs(GridMaster master, int i, int j, int[][] grid, boolean[][] seen, int[][] dirs, char[] charTable, int[] target) {
48 if (master.isTarget()) {
49 target[0] = i;
50 target[1] = j;
51 }
52
53 for (int k = 0; k < 4; k++) {
54 int x = i + dirs[k][0];
55 int y = j + dirs[k][1];
56 char d = charTable[k];
57 char undoD = charTable[(k + 2) % 4];
58 if (master.canMove(d) && grid[x][y] == -1) {
59 grid[x][y] = master.move(d);
60 dfs(master, x, y, grid, seen, dirs, charTable, target);
61 master.move(undoD);
62 }
63 }
64 }
65}
The Java solution is similar to the Python and JavaScript solutions. It first performs DFS to build the grid using the dfs() method. Then, BFS is done using a priority queue (a PriorityQueue object named minHeap ) to find the minimum cost. Finally, the minimum cost is returned or -1 if there is no valid path between the cells.
All the Python, JavaScript and Java solutions follow the same approach and have a similar structure. They utilize DFS for building the grid information and BFS for finding the minimum cost.