题解：动态规划

由于只能向右和向下走，因此，对于坐标$(i,j)$，它一定是由$(i-1,j)$或者$(i,j-1)$位置移动得到，因此定义$f[i][j]$为走到$(i,j)$位置所获得价值的最大值，则有

$f[i][j]=max(f[i-1][j],f[i][j-1])+w[i][j]$

最终，枚举每一个点所获得价值的最大值，如果有$f[i][j]\ge g$，则可以更新最小步数，最小步数即为$(0,0$与$(i,j)$的曼哈顿距离值$dist=i+j$，其中$0\le i\le n,0\le j \le m$

题目内容

采草莓机器人在一个$n*m$的草莓矩阵内，从起点坐标$(0，0)$出发，可以向右或向下两个方向移动，每个方格种植着不同价值的草莓，现在塔子哥规定了一个阈值$g$,代表该机器人此行采集草莓的总价值的最低目标值，塔子哥想知道机器人计算完成任务所需要移动的最少移动次数可以满足这个阈值？

输入描述

第一行输入三个整数:$n,m,g$ , 以空格隔开。

接下来有$n$行，每行有$m$个整数，以空格隔开。这$n*m$ 个数字构成草莓矩阵.

数据范围:

$1\leq n,m \leq 1000,1 \leq a_i \leq 500 , 1 \leq g \leq 1000000$

输出描述

机器人完成任务所需移动的最少次数，不存在则返回-1

示例1

输入

1 1 8
10

输出

0

说明

机器人起点位置即可完成任务，不需要移动

示例2

输入

2 2 5
2 2
2 2

2

说明

需要向右移动一次，再向下移动一次

注意

python用户建议使用pypy3提交