思路与算法

把所有非零植株按花生数递减排列，这个采摘顺序由题目指定。第一株到达用行号时间；之后两株之间走曼哈顿最短路，再花1时间采摘。每次还须预留当前行号的返回路边时间，若下一株连同返回会超时，则结束并输出已有总花生。

正确性说明

非零数量互异，规则固定了唯一的采摘次序。空地没有障碍，横纵步数之和是两株之间最短时间，回路边至少需要当前行号步。只要某前缀可按最短移动采完并返回就可实现；若下一个前缀超时，任何绕路更慢，也不能跳过它去采较少花生，因此无法延长合法前缀。逐次累计得到最多可采数量。

复杂度

O(MN log(MN))时间、O(MN)空间，含植株列表建立与排序。

易错点

每株采摘也耗1时间，进入和返回路边都要计；路边可从任意列进入。不能把它改成自由选点的背包或旅行商问题。K=0及正好能返回的边界分别检查。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, K;
    cin >> n >> m >> K;
    vector<array<int, 3>> a;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            int v;
            cin >> v;
            if (v)
                a.push_back({v, i, j});
        }
    sort(a.rbegin(), a.rend());
    int x = 0, y = 0, time = 0, ans = 0;
    for (auto v : a) {
        int walk = x ? abs(x - v[1]) + abs(y - v[2]) : v[1];
        if (time + walk + 1 + v[1] > K)
            break;
        time += walk + 1;
        x = v[1];
        y = v[2];
        ans += v[0];
    }
    cout << ans << "\n";
}