Shortest Path with Terrain Costs
Each cell of a grid has a terrain cost: cost[r][c] is what it costs to enter that cell, and -1 marks an obstacle. Movement is up, down, left or right. Return the cheapest total cost of a path from src to dst (each [row, col]), or -1 when there is none. The start cell's own cost is not paid.
cost = [[0, 9, 1],
[1, 9, 1],
[1, 1, 1]]
dijkstraGrid(cost, [0, 0], [0, 2]) -> 6 (down and around beats crossing the 9s)
dijkstraGrid([[0, 2, 1]], [0, 0], [0, 2]) -> 3Hints
Hint 1
With unequal costs, the first time BFS reaches a cell is no longer the cheapest. Order the frontier by accumulated cost instead — that's Dijkstra.
Hint 2
Push (cost so far, cell) onto a min-heap; when a popped entry is worse than the best recorded for its cell, skip it.