Cheapest Path Past Closed Cells

Medium2-D Dynamic Programming

Problem

A drone inspects a solar farm laid out as a grid. grid[r][c] is the battery cost of flying over cell (r, c) (a non-negative integer), or -1 if the cell is a no-fly zone. The drone starts at the top-left cell, must finish at the bottom-right cell and moves only right or down.

The cost of a flight is the sum of the costs of every cell visited, including both ends. Return the minimum cost, or -1 if no flight avoids every no-fly zone (this includes a no-fly start or destination).

Example 1

Input:
grid = [[1, 3, -1], [2, -1, 1], [4, 2, 1]]
Output:
10

Both routes through the top row are closed, so the drone goes 1 → 2 → 4 → 2 → 1.

Example 2

Input:
grid = [[0, -1], [-1, 0]]
Output:
-1

Both neighbours of the start are no-fly zones.

Example 3

Input:
grid = [[2, 1, 1], [1, -1, 1], [8, 1, 0]]
Output:
5

Along the top and down the right side: 2 + 1 + 1 + 1 + 0.

Constraints

  • 1 ≤ grid.length, grid[0].length ≤ 200
  • grid[r][c] == -1 or 0 ≤ grid[r][c] ≤ 1000

Hint

Show the first hint

This is the classic cheapest right/down walk, except that some cells cannot be reached at all. How would you represent 'unreachable' in the table?

Walkthrough

How to approach it

01Clarify before coding

  • What if the start or destination is a no-fly zone? Then no flight exists: return -1.
  • Is a cost of 0 allowed? Yes, so 0 cannot double as the 'unreachable' marker.
  • Only right and down moves? Yes, which keeps the dependency graph acyclic and the DP valid.

02Brute force

DFS every right/down path, abandon it when it enters a -1 cell, and track the smallest total at the destination.

Cost: Exponential in m + n; a 200 × 200 farm has more routes than atoms in the universe.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.