How hard is LeetCode 1778. Shortest Path in a Hidden Grid?

LeetCode 1778. Shortest Path in a Hidden Grid is rated Medium on LeetCode.

What is the time complexity of LeetCode 1778. Shortest Path in a Hidden Grid?

The Python solution on this page runs in O(m \times n).

What is the space complexity of LeetCode 1778. Shortest Path in a Hidden Grid?

The Python solution on this page uses O(m \times n) auxiliary space.

What topics does LeetCode 1778. Shortest Path in a Hidden Grid cover?

LeetCode 1778. Shortest Path in a Hidden Grid is tagged Depth-First Search, Breadth-First Search, Array, Interactive and Matrix on LeetCode.

Is LeetCode 1778. Shortest Path in a Hidden Grid a premium problem?

Yes. LeetCode 1778. Shortest Path in a Hidden Grid is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Shortest Path in a Hidden Grid — LeetCode 1778 Python Solution

MediumLeetCode PremiumDepth-First SearchBreadth-First SearchArrayInteractiveMatrix

Problem: #1778
Pattern: Matrix and Grid
Reading time: 9 min
Source: leetcode.com

The problem

This is an interactive problem. There is a robot in a hidden grid, and you are trying to get it from its starting cell to the target cell in this grid.

Example

Input: grid = [[1,2],[-1,0]]
Output: 2
Explanation: One possible interaction is described below:

Python solution

Python

# """
# This is GridMaster's API interface.
# You should not implement it, or speculate about its implementation
# """
# class GridMaster(object):
#    def canMove(self, direction: str) -> bool:
#
#
#    def move(self, direction: str) -> bool:
#
#
#    def isTarget(self) -> None:
#
#


class Solution(object):
    def findShortestPath(self, master: "GridMaster") -> int:
        def dfs(i: int, j: int):
            if master.isTarget():
                nonlocal target
                target = (i, j)
                return
            for k, c in enumerate(s):
                x, y = i + dirs[k], j + dirs[k + 1]
                if master.canMove(c) and (x, y) not in vis:
                    vis.add((x, y))
                    master.move(c)
                    dfs(x, y)
                    master.move(s[(k + 2) % 4])

        s = "URDL"
        dirs = (-1, 0, 1, 0, -1)
        target = None
        vis = set()
        dfs(0, 0)
        if target is None:
            return -1
        vis.discard((0, 0))
        q = deque([(0, 0)])
        ans = -1
        while q:
            ans += 1
            for _ in range(len(q)):
                i, j = q.popleft()
                if (i, j) == target:
                    return ans
                for a, b in pairwise(dirs):
                    x, y = i + a, j + b
                    if (x, y) in vis:
                        vis.remove((x, y))
                        q.append((x, y))
        return -1

Complexity

Measure	Complexity
Time	O(m \times n)
Space	O(m \times n) auxiliary

Pattern: Matrix and Grid

Treat a 2-D grid as a graph whose neighbours are the four adjacent cells. LeetCode 1778. Shortest Path in a Hidden Grid is filed here because LeetCode tags it Matrix, which is the vocabulary this hub collects.

The matrix and grid guide has the Python template for the pattern and the 216 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1778. Shortest Path in a Hidden Grid?: LeetCode 1778. Shortest Path in a Hidden Grid is rated Medium on LeetCode.
What is the time complexity of LeetCode 1778. Shortest Path in a Hidden Grid?: The Python solution on this page runs in O(m \times n).
What is the space complexity of LeetCode 1778. Shortest Path in a Hidden Grid?: The Python solution on this page uses O(m \times n) auxiliary space.
What topics does LeetCode 1778. Shortest Path in a Hidden Grid cover?: LeetCode 1778. Shortest Path in a Hidden Grid is tagged Depth-First Search, Breadth-First Search, Array, Interactive and Matrix on LeetCode.
Is LeetCode 1778. Shortest Path in a Hidden Grid a premium problem?: Yes. LeetCode 1778. Shortest Path in a Hidden Grid is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.