FastPrep
Problem · Matrix

Minimum-Cost Path Through a Weighted Grid

Learn this problem
● MediumVisa logoVisaNEW GRADOA

Problem statement

You are given a rectangular integer grid. A value of -1 marks a blocked cell; every other value is the nonnegative cost of entering that cell.

Start at the top-left cell and reach the bottom-right cell using only up, down, left, or right moves. Return the minimum total cost, including the costs of both the start and destination cells. Return -1 if either endpoint is blocked or no valid path exists.

Function

minimumWeightedGridPathCost(grid: int[][]) → long

Examples

Example 1

grid = [[1,3,1],[1,5,1],[4,2,1]]return = 7

One minimum route has costs 1, 3, 1, 1, and 1 for a total of 7.

Example 2

grid = [[1,-1],[-1,2]]return = -1

The destination is open, but both possible first moves are blocked.

Example 3

grid = [[9]]return = 9

The single cell is both endpoints, so its weight is the complete path cost.

Constraints

  • 1 <= rows, columns <= 500.
  • The grid is rectangular and contains at most 200000 cells.
  • Each value is -1 or lies in [0, 1000000].
  • Every reachable path cost fits a signed 64-bit integer.

More Visa problems

drafts saved locally
public long minimumWeightedGridPathCost(int[][] grid) {
  // write your code here
}
grid[[1,3,1],[1,5,1],[4,2,1]]
expected7
checking account