Assume that the \(K\)-th largest integer is some fixed \(X\).

Use DP (Dynamic Programming) to find for each square the minimum sum of integers greater than or equal to \(X\) if he passes through exactly \(k\) squares when traveling from the initial square to that square.

A set of DP requires an \(O(HWK)\) time, so the overall time complexity is \(O(H^2W^2K)\).

Be careful of the case where there are multiple squares written \(X\).

Sample code (C++)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i = 0; i < n; i++)
void chmin(ll&a,ll b){if(a>b)a=b;}
const ll inf = 1001001001001001001;

int main(){
    int h, w, K; cin >> h >> w >> K;
    vector<vector<int>> grid(h, vector<int>(w));
    rep(i, h) rep(j, w) cin >> grid[i][j];
    ll ans = inf;
    for(auto y : grid) for(auto x : y) {
        vector<vector<vector<ll>>> dp(K + 1, vector<vector<ll>>(h, vector<ll>(w, inf)));
        if(grid[0][0] >= x) dp[1][0][0] = grid[0][0];
        if(grid[0][0] <= x) dp[0][0][0] = 0;
        rep(i, K + 1) rep(j, h) rep(k, w) {
            if(j != h - 1){
                if(i != K && grid[j + 1][k] >= x) chmin(dp[i + 1][j + 1][k], dp[i][j][k] + grid[j + 1][k]);
                if(grid[j + 1][k] <= x) chmin(dp[i][j + 1][k], dp[i][j][k]);
            }
            if(k != w - 1){
                if(i != K && grid[j][k + 1] >= x) chmin(dp[i + 1][j][k + 1], dp[i][j][k] + grid[j][k + 1]);
                if(grid[j][k + 1] <= x) chmin(dp[i][j][k + 1], dp[i][j][k]);
            }
        }
        chmin(ans, dp[K][h - 1][w - 1]);
    }
    cout << ans << endl;
}

bonus: \(O(H^2W^2)\)