You are given an m x n grid. Each cell of grid represents a street. The street of grid[i][j] can be:
1 which means a street connecting the left cell and the right cell.2 which means a street connecting the upper cell and the lower cell.3 which means a street connecting the left cell and the lower cell.4 which means a street connecting the right cell and the lower cell.5 which means a street connecting the left cell and the upper cell.6 which means a street connecting the right cell and the upper cell.
You will initially start at the street of the upper-left cell (0, 0). A valid path in the grid is a path that starts from the upper left cell (0, 0) and ends at the bottom-right cell (m - 1, n - 1). The path should only follow the streets.
Notice that you are not allowed to change any street.
Return true if there is a valid path in the grid or false otherwise.
Example 1:
Input: grid = [[2,4,3],[6,5,2]] Output: true Explanation: As shown you can start at cell (0, 0) and visit all the cells of the grid to reach (m - 1, n - 1).
Example 2:
Input: grid = [[1,2,1],[1,2,1]] Output: false Explanation: As shown you the street at cell (0, 0) is not connected with any street of any other cell and you will get stuck at cell (0, 0)
Example 3:
Input: grid = [[1,1,2]] Output: false Explanation: You will get stuck at cell (0, 1) and you cannot reach cell (0, 2).
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 3001 <= grid[i][j] <= 6The BFS approach involves using a queue to explore cells level by level. The idea is to start from the top-left corner and explore each connected component, following the constraints of the streets on the grid. We keep track of visited cells to avoid cycles as we traverse the grid. The queue helps in checking all possible neighbors for each cell, and the goal is to see if we can reach the bottom-right corner.
The solution uses a queue for BFS to explore the grid starting from (0, 0). At each cell, it checks valid moves based on the current street type and explores connected components. If we reach the bottom-right cell, the function returns true.
Java
Time Complexity: O(m * n), because each cell is visited at most once.
Space Complexity: O(m * n), for the visited set and the queue.
The Depth-First Search (DFS) approach involves recursive exploration of each path starting from the top-left corner. For every cell, based on its street type, we explore all possible connected directions. Recursive backtracking helps explore each path completely before marking it as visited. The idea is to check if it is possible to reach the bottom-right corner using valid paths as per street constraints.
This C++ solution uses recursive DFS to explore potential paths from each cell based on the street type. It uses backtracking to continue exploring the grid until the target cell is found or all paths are exhausted.
JavaScript
Time Complexity: O(m * n), for visiting every cell once recursively in the worst case.
Space Complexity: O(m * n), due to the recursive call stack and the visited map.
| Approach | Complexity |
|---|---|
| Breadth-First Search (BFS) | Time Complexity: O(m * n), because each cell is visited at most once. |
| Depth-First Search (DFS) | Time Complexity: O(m * n), for visiting every cell once recursively in the worst case. |
Find the Safest Path in a Grid - Leetcode 2812 - Python • NeetCodeIO • 16,674 views views
Watch 9 more video solutions →Practice Check if There is a Valid Path in a Grid with our built-in code editor and test cases.
Practice on FleetCode