Problem
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 orfalse
otherwise.
Examples
Example 1
|
|
Example 2
|
|
Example 3
|
|
Constraints
m == grid.length
n == grid[i].length
1 <= m, n <= 300
1 <= grid[i][j] <= 6
Solution
Method 1 – BFS/DFS with Direction Mapping
Intuition
Each cell type allows movement in certain directions, and only if the adjacent cell allows entry from that direction. We can use BFS or DFS to traverse the grid, only moving to valid neighboring cells according to the street types.
Reasoning
For each cell, we check all possible directions it can move to, and for each move, verify that the next cell allows entry from the opposite direction. If we can reach the bottom-right cell, a valid path exists. This works because the grid is small and each move is strictly determined by the street types.
Approach
- Define the allowed directions for each street type and the required entry direction for each type.
- Use BFS or DFS starting from (0,0), marking visited cells.
- For each move, check if the next cell is within bounds, not visited, and allows entry from the current direction.
- If we reach (m-1, n-1), return true. If BFS/DFS ends, return false.
Edge cases:
- Single cell grid: always true.
- No valid moves from the start: false.
Code
|
|
|
|
|
|
|
|
|
|
Complexity
- ⏰ Time complexity:
O(m * n)
, as each cell is visited at most once and each move is constant time. - 🧺 Space complexity:
O(m * n)
, as we store the visited grid and BFS/DFS queue.