1030. Dijkstra on Grid — Minimum Cost Path

Given a grid of non-negative cell costs, return the minimum total cost to travel from the top-left cell (0,0) to the bottom-right cell, moving 4-directionally, where a path's cost is the sum of all cells it visits (including both endpoints). The input is JSON {grid}.

Input: JSON {grid}.

Output: Integer — the minimum path cost.

Examples

Input: {"grid":[[1,3,1],[1,5,1],[4,2,1]]}
Output: 7
Explanation: 1+3+1+1+1=7 along the top-right route.

Input: {"grid":[[5]]}
Output: 5
Explanation: Single cell.

Input: {"grid":[[1,2],[3,4]]}
Output: 7
Explanation: 1+2+4 or 1+3+4.

Constraints

• 1<=rows,cols<=200
• costs >= 0

Asked by