Leetcode Problem 1391. Check if There is a Valid Path in a Grid

1391. Check if There is a Valid Path in a Grid

Leetcode Solutions

Depth-First Search (DFS) Approach

  1. Create a helper function dfs that takes the current cell's coordinates (i, j) and the grid as parameters.
  2. If the current cell is out of bounds or has been visited, return false.
  3. If the current cell is the destination cell (m - 1, n - 1), return true.
  4. Mark the current cell as visited.
  5. Based on the value of the current cell, determine the possible directions to move (left, right, up, down).
  6. For each possible direction, check if the next cell can be reached from the current cell (i.e., the street connections match).
  7. Recursively call dfs for the next cell.
  8. If any recursive call returns true, propagate this result back up the call stack.
  9. If no valid path is found, backtrack by unmarking the current cell as visited and return false.
  10. Call dfs from the starting cell (0, 0) and return its result.
UML Thumbnail

Breadth-First Search (BFS) Approach

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...