Infinite Booster
InterviewTime limit1sMemory limit512 MB
On an N by M grid of booster counts, move only right or down within the count of the cell you last stopped on, minimizing the number of stopping cells from (1,1) to (N,M).
- Level
Medium7 of 10
- Topics
- Dynamic programming, Graph, BFS, Matrix
- Solved
- No attempts yet
Problem
Jeongbeom, a beginner Kartrider player, is growing more disappointed with the difficult controls. Tired of hard techniques such as drifting, instant boosters, cutting, and toktok, he decides to try the somewhat easier "Sublime Infinite Booster Mode."
"Sublime Infinite Booster Mode" takes place on a rectangular map of size N × M, made up entirely of unit cells. Unlike the original "Infinite Booster Mode," every cell contains a certain number of booster items. Play proceeds as follows.
At the start, the player's kart is stopped at the starting point, row 1 column 1, and holds 0 booster items. The goal is to reach the destination cell at row N column M, and the game ends as soon as the kart arrives. When the kart is stopped on a cell, it automatically picks up all booster items on that cell. If it picks up x items, it can choose one direction and move at most x cells to the right or at most x cells downward, moving one cell at a time. For example, with 3 booster items, moving 2 cells right or 3 cells down is possible, but moving 1 cell right and then 2 cells down, moving 1 cell left, or moving 2.718 cells down is not possible. When the kart stops after moving, all booster items it held are consumed.
Booster items on cells that the kart passes over without stopping cannot be picked up, and the kart cannot move in a direction that leaves the map.
Jeongbeom wants to minimize the number of cells where he picks up booster items while traveling from the starting point to the destination in "Sublime Infinite Booster Mode." Help Jeongbeom.
Input
The first line gives the map's height and width as positive integers N and M, separated by a space. (1 ≤ N, M ≤ 300)
From the second line, N lines follow. Each line contains M positive integers aij, the number of booster items in each cell, separated by spaces. (1 ≤ aij ≤ max(N, M)) aij is the number of booster items in the cell at row i column j.
The starting point and the destination are different.
Output
On the first line, output the minimum number of cells where Jeongbeom picks up booster items while traveling from the starting point to the destination.