Snail Cheapest Routes

Medium · dynamic programming

A snail lives in an allotment laid out as a grid with m rows and n columns. grid[r][c] describes the plot in row r and column c:

a number from 0 to 100 is how much effort it takes to cross that plot,
-1 means the plot is flooded and the snail cannot enter it.

The snail starts on the top-left plot and wants to reach the bottom-right plot. From any plot it can only move one plot right or one plot down. The effort of a route is the sum of the efforts of every plot on it, including the first and the last.

Return a list of two numbers: the lowest effort of any route, and the number of different routes that have exactly that effort, modulo 10^9 + 7. Two routes are different if they visit different plots.

If the snail cannot get from the start to the finish (including when either of those plots is flooded), return [-1, 0].

Examples

Example 1

Input: grid = [[1, 3, 1], [1, 5, 1], [4, 2, 1]]

Output: [7, 1]

Right, right, down, down visits 1, 3, 1, 1, 1 for a total of 7. Every other route costs more, so there is exactly one cheapest route.

Example 2

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

Output: [8, 2]

The middle plot is flooded. Over the top (1 + 2 + 3 + 1 + 1) and round the bottom (1 + 4 + 1 + 1 + 1) both cost 8, and no route is cheaper.

Example 3

Input: grid = [[2, -1], [-1, 5]]

Output: [-1, 0]

Both neighbours of the start are flooded, so the snail is stuck.

Constraints

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