The Cheapest Walk Across a Toll Grid
Implement cheapestWalk
You are given a grid of positive costs. Starting on the top-left cell, walk up, down, left or right to reach the bottom-right cell, paying the value of every cell you enter (including the start). Find the smallest total cost.
Because the cheapest walk may go away from the goal to avoid expensive cells, a dynamic programming pass over the grid is not enough. This is a shortest path problem on a weighted graph whose nodes are the cells, so Dijkstra's algorithm applies.
Example 1:
Input: costs = [[3,1,4,2],[2,7,1,8],[5,2,6,1]]
Output: 16
Example 2:
Input: costs = [[4]]
Output: 4
Example 3:
Input: costs = [[1,9,1],[1,9,1],[1,1,1]]
Output: 5
+ 13 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ rows, cols ≤ 5; 1 ≤ costs[r][c] ≤ 9 - ●
You start on the top-left cell and must reach the bottom-right cell, moving up, down, left or right (you may move in any of the four directions, also away from the goal) - ●
Entering a cell costs its value; the value of the starting cell is also paid - ●
Return the smallest total cost of a walk from the start cell to the destination cell
costs =
[[3,1,4,2], [2,7,1,8], [5,2,6,1]]