Minimum Path Cost in a Hidden Grid

To solve this problem, follow these steps:

Mapping the Grid: Since the dimensions of the grid are not known, you’ll need to explore and map it. You can use Depth First Search (DFS) to achieve this. The DFS function should also identify the target cell and its cost.
Finding the Minimum Cost Path: Once the grid is mapped, you’ll need to find the minimum total cost to get to the target cell from the starting cell. You can use Dijkstra’s algorithm, which works with weighted graphs and finds the shortest path.

Python solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
from collections import deque
import heapq

class Solution(object):
    def findShortestPath(self, master: 'GridMaster') -> int:
        directions = {'U': (-1, 0), 'D': (1, 0), 'L': (0, -1), 'R': (0, 1)}
        reverse_directions = {'U': 'D', 'D': 'U', 'L': 'R', 'R': 'L'}
        grid = {}

        # Function to map the grid
        def dfs(x, y):
            if (x, y) in grid:
                return
            grid[(x, y)] = 0
            for d, (dx, dy) in directions.items():
                if master.canMove(d):
                    cost = master.move(d)
                    if master.isTarget():
                        grid[(x + dx, y + dy)] = cost
                        self.target = (x + dx, y + dy)
                    else:
                        dfs(x + dx, y + dy)
                        grid[(x + dx, y + dy)] = cost
                    master.move(reverse_directions[d])

        # Step 1: Mapping the grid
        self.target = None
        dfs(0, 0)

        # Check if target was found
        if self.target is None:
            return -1

        # Step 2: Finding the minimum cost path using Dijkstra's algorithm
        min_heap = [(0, 0, 0)] # (cost, x, y)
        seen = set()
        while min_heap:
            cost, x, y = heapq.heappop(min_heap)
            if (x, y) in seen:
                continue
            seen.add((x, y))
            if (x, y) == self.target:
                return cost
            for dx, dy in directions.values():
                nx, ny = x + dx, y + dy
                if (nx, ny) in grid and (nx, ny) not in seen:
                    heapq.heappush(min_heap, (cost + grid[(nx, ny)], nx, ny))

        return -1

This code first maps the entire grid using a DFS algorithm. Then, it uses Dijkstra’s algorithm to find the minimum total cost path from the starting cell to the target cell. If there is no valid path between the cells, it returns -1.

Complexity Analysis

Time Complexity: (O(E + V \log V)), where (E) is the number of edges and (V) is the number of vertices in the grid. In the worst case, (E \approx V) and thus the time complexity can be approximated as (O(V \log V)).
Space Complexity: (O(V)), as the algorithm stores the grid and visited nodes, both of which contain at most (V) entries.