Leetcode Problem 1368. Minimum Cost to Make at Least One Valid Path in a Grid

1368. Minimum Cost to Make at Least One Valid Path in a Grid

Leetcode Solutions

BFS and DFS

  1. Initialize a 2D array dp with high values (infinity) to store the minimum cost to reach each cell.
  2. Perform a DFS from the top-left corner (0,0), marking reachable cells with cost 0 and adding them to a BFS queue.
  3. While the BFS queue is not empty: a. Increment the cost (since we are changing direction). b. For each cell in the BFS queue, try changing the direction to all 3 other directions. c. If the new direction is valid and not visited, update the minimum cost and add the cell to the BFS queue.
  4. Continue until all cells are visited.
  5. Return the minimum cost to reach the bottom-right corner.
UML Thumbnail

- BFS - Simple Solution

Ask Question

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

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...