Two Couriers, No Meeting

Hard · dynamic programming

A city is a grid of blocks with m rows and n columns. grid[r][c] describes the block in row r and column c:

a number from 0 to 100 is the toll to drive through that block,
-1 means the road is closed and nobody can enter it.

Two couriers both start at the top-left block and both must finish at the bottom-right block. Each courier moves one block right or one block down at a time, and the two make their moves together, one block each per step.

The couriers must never be in the same block, except the start block and the finish block, which they share. A toll is paid every time a block is driven through, but the shared start and finish are paid only once.

Return the smallest total toll that the two couriers can pay together. If there is no way to send them without them meeting (including when the start or the finish is closed), return -1.

Examples

Example 1

Input: grid = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

Output: 38

One courier goes right, right, down, down (tolls 2 + 3 + 6), the other down, right, down, right (4 + 5 + 8). Add the start and the finish, 1 + 9, for 38. They never meet in between.

Example 2

Input: grid = [[0, 1], [2, 0]]

Output: 3

One courier goes through the top-right block (toll 1), the other through the bottom-left block (toll 2). The start and finish cost 0.

Example 3

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

Output: -1

Only the top road is open. Both couriers would have to drive through the same blocks.

Constraints

1 <= m, n <= 40
-1 <= grid[r][c] <= 100