Minimum Path Cost In a Hidden Grid
Media.netThe problem
You are given a grid with an unknown structure and a GridMaster API with the following methods:
-
boolean canMove(char direction) : Returns **true **if you can move in the given direction ('U', 'D', 'L', 'R'); otherwise, returns false.
-
int move(char direction) : Moves in the given direction and returns the cost of the move. If the move is invalid, it returns -1.
-
boolean isTarget() : Returns **true **if the current position is the target; otherwise, returns false.
Your task is to implement a function that uses this API to find the **minimum **path cost from the starting position to the target.
Input : grid = [[2,3],[1,1]], r1 = 0, c1 = 1, r2 = 1, c2 = 0 Output : 2 Explanation : One possible interaction is described below: The robot is initially standing on cell (0, 1), denoted by the 3.
- master.canMove('U') returns false.
- master.canMove('D') returns true.
- master.canMove('L') returns true.
- master.canMove('R') returns false.
- master.move('L') moves the robot to the cell (0, 0) and returns 2.
- master.isTarget() returns false.
- master.canMove('U') returns false.
- master.canMove('D') returns true.
- master.canMove('L') returns false.
- master.canMove('R') returns true.
- master.move('D') moves the robot to the cell (1, 0) and returns 1.
- master.isTarget() returns true.
- master.move('L') doesn't move the robot and returns -1.
- master.move('R') moves the robot to the cell (1, 1) and returns 1.
- We now know that the target is the cell (1, 0), and the minimum total cost to reach it is 2.
**Input : **grid = [[0,3,1],[3,4,2],[1,2,0]], r1 = 2, c1 = 0, r2 = 0, c2 = 2 Output : 9 Explanation : The minimum cost path is (2,0) -> (2,1) -> (1,1) -> (1,2) -> (0,2).
Input : grid = [[1,0],[0,1]], r1 = 0, c1 = 0, r2 = 1, c2 = 1
- 1 <= n, m <= 100
- m == grid.length
- n == grid[i].length
- 0 <= grid[i][j] <= 100
cpp
/**
* // This is the GridMaster's API interface.
* // You should not implement it, or speculate about its implementation
* class GridMaster {
* public:
* bool canMove(char direction);
* int move(char direction);
* boolean isTarget();
* };
*/
class Solution {
public:
int findShortestPath(GridMaster &master) {
//Your Code Goes Here
}
};java
/**
* // This is the GridMaster's API interface.
* // You should not implement it, or speculate about its implementation
* class GridMaster {
* boolean canMove(char direction);
* int move(char direction);
* boolean isTarget();
* }
*/
class Solution {
public int findShortestPath(GridMaster master) {
//Your Code Goes Here
}
}python
# """
# This is GridMaster's API interface.
# You should not implement it, or speculate about it's implementation
# """
#class GridMaster(object):
# def canMove(self, direction):
# """
# :type direction: str
# :rtype bool
# """
#
# def move(self, direction):
# """
# :type direction: str
#. :rtype int
# """
#
# def isTarget(self):
# """
# :rtype bool
# """
#
class Solution(object):
def findShortestPath(self, master):
"""
:type master: GridMaster
:rtype: int
"""
#Your Code Goes Herejavascript
class Solution {
findShortestPath(master) {
}
}csharp
/**
* // This is the GridMaster's API interface.
* // You should not implement it, or speculate about its implementation
* class GridMaster {
* public:
* bool canMove(char direction);
* int move(char direction);
* boolean isTarget();
* };
*/
class Solution {
public int FindShortestPath(GridMaster master) {
}
}go
func findShortestPath(master GridMaster) int {
}Stuck? Show a way to structure it+
- 01DFS from the start and map reachable cells.
- 02After every successful exploration move, backtrack exactly.
- 03Mark the target when discovered.
- 04Run BFS on the discovered graph.
- 05Return target distance or failure.
Reference answer
Then expect these follow-ups
How would weighted moves change the second phase?
Tests: Dijkstra
How do you encode coordinates safely?
Tests: hashing
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question