Leetcode Problem 2812. Find the Safest Path in a Grid

2812. Find the Safest Path in a Grid

Leetcode Solutions

Binary Search with BFS

  1. Initialize a 2D array distToThief with the same dimensions as grid to store the minimum Manhattan distance from each cell to the nearest thief.
  2. Perform a multi-source BFS starting from all the thief cells to populate distToThief.
  3. Use binary search to find the maximum safeness factor. Set low to 0 and high to the maximum value in distToThief.
  4. In each iteration of binary search, use the mid-value as the candidate safeness factor.
  5. Perform BFS from the top-left corner to check if there is a valid path to the bottom-right corner with the safeness factor at least equal to the candidate.
  6. If a valid path exists, update low to mid + 1; otherwise, update high to mid - 1.
  7. Continue the binary search until low exceeds high.
  8. The maximum safeness factor is the last valid mid value found during binary search.
UML Thumbnail

Dijkstra's Algorithm

Ask Question

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

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...