Problem statement

https://leetcode.com/problems/shortest-path-in-a-hidden-grid/

Solution

In this problem we need to find the shortest distance, however we can not use bfs, because we can not move at several cells in the same time. So the only choice we have is the following:

  1. Perform dfs and save traversed graph.
  2. Run bfs on saved graph and find the shortest distance.

Complexity

Time complexity is O(mn) as well as space complexity.

Code

class Solution:
    def findShortestPath(self, master):
        dirs = [("U", -1, 0), ("D", 1, 0), ("L", 0, -1), ("R", 0, 1)]
        back = {"U": "D", "D": "U", "L": "R", "R": "L"}
        
        G = {(0, 0): master.isTarget()}
        
        def dfs(x, y):
            for d, dx, dy in dirs:
                x1, y1 = x + dx, y + dy
                if (x1, y1) not in G and master.canMove(d):
                    master.move(d)
                    G[x1, y1] = master.isTarget()
                    dfs(x1, y1)
                    master.move(back[d])
                    
        dfs(0, 0)
        
        queue = deque([(0, 0, 0)])
        visited = set()
        
        while queue:
            dist, x, y = queue.popleft()
            if G[x, y]: return dist
            
            for dx, dy in (x+1, y), (x, y+1), (x-1, y), (x, y-1):
                if (dx, dy) not in G or (dx, dy) in visited: continue
                visited.add((dx, dy))
                queue.append((dist + 1, dx, dy))
                
        return -1