All problems

Warehouse Robot Turns

Medium · dynamic programming

A warehouse floor is a grid of tiles. grid[r][c] is the cost of driving over the tile in row r and column c, and it is never negative.

A robot starts on the top-left tile and has to reach the bottom-right tile. Every step moves it one tile right or one tile down. It pays the cost of every tile it drives over, including the first and the last.

The robot's steering is worn out, so it can only change direction a limited number of times. A turn is a step whose direction differs from the step before it (right then down, or down then right). The first step is never a turn. The robot may make at most turns turns on its way.

Return the smallest total cost of a route with at most turns turns. If there is no such route, return -1. If the grid has a single tile, the route is just that tile.

Examples

Example 1

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

Output: 21

With one turn the robot goes right along the top and then down: 1 + 2 + 3 + 6 + 9.

Example 2

Input: grid = [[1, 1, 9, 9], [9, 1, 9, 9], [9, 1, 1, 1]], turns = 2

Output: 6

Right, down twice, then right twice is two turns and costs 1 + 1 + 1 + 1 + 1 + 1.

Example 3

Input: grid = [[1, 2], [3, 4]], turns = 0

Output: -1

Without turning the robot can only go along an edge, and that never reaches the opposite corner of a 2 by 2 floor.

Constraints