✏️
leetcode solution
  • Leetcode Solutions
  • LeetCode 1. Two Sum
  • LeetCode 2. Add Two Numbers
  • LeetCode 3. Longest Substring Without Repeating Characters
  • LeetCode 4. Median of Two Sorted Arrays
  • LeetCode 5. Longest Palindromic Substring
  • LeetCode 6. ZigZag Conversion
  • LeetCode 7. Reverse Integer
  • LeetCode 8. String to Integer (atoi)
  • LeetCode 9. Palindrome Number
  • LeetCode 10. Regular Expression Matching
  • LeetCode 11. Container With Most Water
  • LeetCode 12. Integer to Roman
  • LeetCode 13. Roman to Integer
  • LeetCode 14. Longest Common Prefix
  • LeetCode 15. 3Sum
  • LeetCode 16. 3Sum Closest
  • LeetCode 17. Letter Combinations of a Phone Number
  • LeetCode 18. 4Sum
  • LeetCode 19. Remove Nth Node From End of List
  • LeetCode 20. Valid Parentheses
  • LeetCode 21. Merge Two Sorted Lists
  • LeetCode 22. Generate Parentheses
  • LeetCode 23. Merge k Sorted Lists
  • LeetCode 24. Swap Nodes in Pairs
  • LeetCode 25. Reverse Nodes in k-Group
  • LeetCode 26. Remove Duplicates from Sorted Array
  • LeetCode 27. Remove Element
  • LeetCode 28. Implement strStr()
  • LeetCode 29. Divide Two Integers
  • LeetCode 30. Substring with Concatenation of All Words
  • LeetCode 31. Next Permutation
  • LeetCode 32. Longest Valid Parentheses
  • LeetCode 33. Search in Rotated Sorted Array
  • LeetCode 42. Trapping Rain Water
  • LeetCode 56. Merge Intervals
  • LeetCode 67. Add Binary
  • LeetCode 81. Search in Rotated Sorted Array II
  • LeetCode 124. Binary Tree Maximum Path Sum
  • LeetCode 125. Valid Palindrome
  • LeetCode 153. Find Minimum in Rotated Sorted Array
  • LeetCode 154. Find Minimum in Rotated Sorted Array II
  • LeetCode 157. Read N Characters Given Read4
  • LeetCode 158. Read N Characters Given Read4 II - Call multiple times
  • LeetCode 236. Lowest Common Ancestor of a Binary Tree
  • LeetCode 238. Product of Array Except Self
  • LeetCode 269. Alien Dictionary
  • Leetcode 295. Find Median from Data Stream
  • Leetcode 297. Serialize and Deserialize Binary Tree
  • LeetCode 300. Longest Increasing Subsequence
  • LeetCode 301. Remove Invalid Parentheses
  • LeetCode 336. Palindrome Pairs
  • LeetCode 407. Trapping Rain Water II
  • LeetCode 415. Add Strings
  • LeetCode 426. Convert Binary Search Tree to Sorted Doubly Linked List
  • LeetCode 489. Robot Room Cleaner
  • LeetCode 560. Subarray Sum Equals K
  • LeetCode 680. Valid Palindrome II
  • LeetCode 710. Random Pick with Blacklist
  • LeetCode 721. Accounts Merge
  • LeetCode 863. All Nodes Distance K in Binary Tree
  • LeetCode 918. Maximum Sum Circular Subarray
  • LeetCode 953. Verifying an Alien Dictionary
  • LeetCode 973. K Closest Points to Origin
  • LeetCode 1249. Minimum Remove to Make Valid Parentheses
  • LeetCode 1428. Leftmost Column with at Least a One
  • LeetCode 1570. Dot Product of Two Sparse Vectors
  • LeetCode 1644. Lowest Common Ancestor of a Binary Tree II
  • LeetCode 1650. Lowest Common Ancestor of a Binary Tree III
  • LeetCode 1676. Lowest Common Ancestor of a Binary Tree IV
  • Leetcode 1727. Largest Submatrix With Rearrangements
  • LeetCode 1751. Maximum Number of Events That Can Be Attended II
  • LeetCode 1754. Largest Merge Of Two Strings
  • LeetCode 1755. Closest Subsequence Sum
  • LeetCode 1760. Minimum Limit of Balls in a Bag
  • LeetCode 1761. Minimum Degree of a Connected Trio in a Graph
  • LeetCode 1764. Form Array by Concatenating Subarrays of Another Array
  • LeetCode 1765. Map of Highest Peak
  • LeetCode 1766. Tree of Coprimes
  • LeetCode 1770. Maximum Score from Performing Multiplication Operations
  • LeetCode 1771. Maximize Palindrome Length From Subsequences
  • LeetCode 1774. Closest Dessert Cost
  • LeetCode. 1775 Equal Sum Arrays With Minimum Number of Operations
  • LeetCode 1776. Car Fleet II
  • LeetCode 1778. Shortest Path in a Hidden Grid
  • LeetCode 1779. Find Nearest Point That Has the Same X or Y Coordinate
  • LeetCode 1780. Check if Number is a Sum of Powers of Three
  • LeetCode 1781. Sum of Beauty of All Substrings
  • LeetCode 1782. Count Pairs Of Nodes
  • LeetCode 1784. Check if Binary String Has at Most One Segment of Ones
  • LeetCode 1785. Minimum Elements to Add to Form a Given Sum
  • LeetCode 1786. Number of Restricted Paths From First to Last Node
  • LeetCode 1787. Make the XOR of All Segments Equal to Zero
  • LeetCode 1788. Maximize the Beauty of the Garden
  • LeetCode 1790. Check if One String Swap Can Make Strings Equal
  • LeetCode 1791. Find Center of Star Graph
  • LeetCode 1792. Maximum Average Pass Ratio
  • LeetCode 1793. Maximum Score of a Good Subarray
  • LeetCode 1794. Count Pairs of Equal Substrings With Minimum Difference
  • LeetCode 1796. Second Largest Digit in a String
  • LeetCode 1797. Design Authentication Manager
  • LeetCode 1798. Maximum Number of Consecutive Values You Can Make
  • LeetCode 1799. Maximize Score After N Operations
  • LeetCode 1800. Maximum Ascending Subarray Sum
  • LeetCode 1801. Number of Orders in the Backlog
  • LeetCode 1802. Maximum Value at a Given Index in a Bounded Array
  • LeetCode 1803. Count Pairs With XOR in a Range
  • LeetCode 1804. Implement Trie II (Prefix Tree)
  • LeetCode 1805. Number of Different Integers in a String
  • LeetCode 1807. Evaluate the Bracket Pairs of a String
  • LeetCode 1808. Maximize Number of Nice Divisors
  • LeetCode 1810. Minimum Path Cost in a Hidden Grid
  • LeetCode 1812. Determine Color of a Chessboard Square
  • LeetCode 1813. Sentence Similarity III
  • LeetCode 1814. Count Nice Pairs in an Array
  • LeetCode 1815. Maximum Number of Groups Getting Fresh Donuts
  • LeetCode 1816. Truncate Sentence
  • LeetCode 1817. Finding the Users Active Minutes
  • LeetCode 1818. Minimum Absolute Sum Difference
  • LeetCode 1819. Number of Different Subsequences GCDs
  • LeetCode 1820. Maximum Number of Accepted Invitations
  • LeetCode 1822. Sign of the Product of an Array
  • LeetCode 1824. Minimum Sideway Jumps
  • LeetCode 1825. Finding MK Average
  • LeetCode 1826. Faulty Sensor
  • LeetCode 1827. Minimum Operations to Make the Array Increasing
  • LeetCode 1828. Queries on Number of Points Inside a Circle
  • LeetCode 1829. Maximum XOR for Each Query
  • LeetCode 1830. Minimum Number of Operations to Make String Sorted
  • LeetCode 1832. Check if the Sentence Is Pangram
  • LeetCode 1833. Maximum Ice Cream Bars
  • LeetCode 1834. Single-Threaded CPU
  • LeetCode 1835. Find XOR Sum of All Pairs Bitwise AND
  • LeetCode 1836. Remove Duplicates From an Unsorted Linked List
  • LeetCode 1837. Sum of Digits in Base K
  • LeetCode 1839. Longest Substring Of All Vowels in Order
  • LeetCode 1840. Maximum Building Height
  • LeetCode 1847. Closest Room
  • LeetCode 1850. Minimum Adjacent Swaps to Reach the Kth Smallest Number
  • LeetCode 1851. Minimum Interval to Include Each Query
Powered by GitBook
On this page

Was this helpful?

LeetCode 1778. Shortest Path in a Hidden Grid

DFS+BFS

This is an interactive problem.

You are given a robot in a hidden grid, and it wants to go to a target cell in this grid. The grid is of size m x n, and each cell in the grid can be empty or blocked. It is guaranteed that the start point and the robot's destination are different, and neither of them is blocked.

You want to find the robot's minimum distance to the target cell. However, you do not know the grid's dimensions, or the starting point of the robot, or its target destination. You are only allowed to ask queries to your GridMaster object.

You are given a class GridMaster which you can call the following functions from:

  • boolean GridMaster.canMove(char direction) returns trueif the robot can move in that direction. Otherwise, it returns false.

  • void GridMaster.move(char direction) moves the robot in that direction. If this move would move the robot to a blocked cell or off the grid, it will be ignored, and the robot would remain in the same position.

  • boolean GridMaster.isTarget() returns true if the robot is currently on the target cell. Otherwise, it returns false.

Note that direction in the above functions should be a character from {'U','D','L','R'}, representing the directions up, down, left, and right, respectively.

Return the minimum distance between the robot's initial starting cell and the target cell if there is a path between them. Otherwise, return -1.

Custom testing:

The test input is read as a 2D matrix grid of size m x n where:

  • grid[i][j] == -1 indicates that the robot is in cell (i, j).

  • grid[i][j] == 0 indicates that the cell (i, j) is blocked.

  • grid[i][j] == 1 indicates that the cell (i, j) is empty.

  • grid[i][j] == 2 indicates that the cell (i, j) is the target cell.

There is exactly one -1 and 2 in grid. Remember that you will not have this information in your code.

Example 1:

Input: grid = [[1,2],[-1,0]]
Output: 2
Explanation: One possible interaction is described below:
The robot is initially standing on cell (1, 0), denoted by the -1.
- master.canMove('U') returns True.
- master.canMove('D') returns False.
- master.canMove('L') returns False.
- master.canMove('R') returns False.
- master.move('U') moves the robot to the cell (0, 0).
- 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('R') moves the robot to the cell (0, 1).
- master.isTarget() returns True. 
We now know that the target is the cell (0, 1), and the shortest path to the target is 2.

Example 2:

Input: grid = [[0,0,-1],[1,1,1],[2,0,0]]
Output: 4
Explanation: The minimum distance between the robot and the target is 4.

Example 3:

Input: grid = [[-1,0],[0,2]]
Output: -1
Explanation: There is no path from the robot to the target cell.

Constraints:

  • m == grid.length

  • n == grid[i].length

  • 1 <= n, m <= 500

  • grid[i][j] is either -1, 0, 1, or 2.

  • There is exactly one -1 in grid.

  • There is exactly one 2 in grid.

Solution:

/**
 * // This is the GridMaster's API interface.
 * // You should not implement it, or speculate about its implementation
 * class GridMaster {
 *   public:
 *     bool canMove(char direction);
 *     void move(char direction);
 *     boolean isTarget();
 * };
 */

class Solution {
public:
    // 0 is blocked, 1 is empty, 2 is target
    void ConstructGrid(vector<vector<int>>& grid, GridMaster &master, int row, int col, const map<char, pair<int, int>>& directions) {
        grid[row][col] = 1;
        if (master.isTarget()) {
            grid[row][col] = 2;
        }
        
        for (const auto& direction : directions) {
            int new_row = row + direction.second.first;
            int new_col = col + direction.second.second;
            if (grid[new_row][new_col] != -1) {
                continue;
            }
            if (master.canMove(direction.first)) {
                master.move(direction.first);
                ConstructGrid(grid, master, new_row, new_col, directions);
                if (direction.first == 'U') master.move('D');
                else if (direction.first == 'D') master.move('U');
                else if (direction.first == 'L') master.move('R');
                else master.move('L');
            } else {
                grid[new_row][new_col] = 0;
            }
        }
    }
    
    int findShortestPath(GridMaster &master) {
        map<char, pair<int, int>> directions = {
            {'U', {0, 1}},
            {'D', {0, -1}},
            {'L', {-1, 0}},
            {'R', {1, 0}},
        };
        
        vector<vector<int>> grid(1001, vector<int>(1001, -1));
        ConstructGrid(grid, master, 501, 501, directions);
        
        queue<pair<int, int>> myqueue;
        myqueue.push({501, 501});
        grid[501][501] = 0;
        
        int distance = 1;
        while (!myqueue.empty()) {
            int queue_size = myqueue.size();
            for (int k = 0; k < queue_size; k++) {
                pair<int, int> cur = myqueue.front();
                myqueue.pop();
                
                for (const auto& direction : directions) {
                    int new_row = cur.first + direction.second.first;
                    int new_col = cur.second + direction.second.second;
                    if (grid[new_row][new_col] == 2) {
                        return distance;
                    }
                    if (grid[new_row][new_col] <= 0) {
                        continue;
                    }
                    // Mark as 'visited'.
                    grid[new_row][new_col] = 0;
                    myqueue.push({new_row, new_col});
                }
            }
            
            distance++;
        }
        
        return -1;
    }
};
PreviousLeetCode 1776. Car Fleet IINextLeetCode 1779. Find Nearest Point That Has the Same X or Y Coordinate

Last updated 4 years ago

Was this helpful?

English Version in Youtube
中文版解答Youtube Link
中文版解答Bilibili Link