問題概要

$H \times W$ のグリッドが与えられ、各マス $(i, j)$ には値 $A_{i, j}$ 　が書かれている。

グリッドから異なる 2 マス $(a, b), (c, d)$ を選ぶとする。その 2 マスのスコアは、定数 $C$ が与えられて、

$A_{a, b} + A_{c, d} + C(|a - c| + |b - d|)$

で与えられる。このスコアの最小値を求めよ。

制約

$2 \le H, W \le 1000$

考えたこと (一言)

2 点の配置は (左上, 右下) と (右上, 左下) という 2 パターンがある。これらは両方とも試して、小さい方を答えればよい。(右上, 左下) を試す方については、盤面全体を左右反転して、同じメソッドを繰り返せばよい。

以降、(左上, 右下) という配置に限定して考えることができる。

そうすると、いかにも「グリッド上の DP」が使えそうだ。

dp[i][j] ← マス $(i, j)$ よりも左上方向にあるマス $(a, b)$ を始点として、 $A_{a, b} + C(|a - i| + |b - j|)$ の値の最小値

ポイントは、マンハッタン距離 $C(|a - i| + |b - j|)$ の部分は、始点から終点へと向かうパスを 1 伸ばすごとにコスト $C$ が加算するのだと言い換えること。

あとは、この DP を実装すれば正解になる。計算量は $O(HW)$ となる。

コード

#include <bits/stdc++.h>
using namespace std;
const long long INF = 1LL<<60;

bool chmin(long long& a, long long b) { if (a > b) { a = b; return 1; } return 0; }

int main() {
    long long H, W, C;
    cin >> H >> W >> C;
    vector<vector<long long>> A(H, vector<long long>(W));
    for (int i = 0; i < H; ++i) for (int j = 0; j < W; ++j) cin >> A[i][j];
    
    long long res = INF;
    for (int iter = 0; iter < 2; ++iter) {
        vector<vector<long long>> dp(H, vector<long long>(W, INF));
        for (int i = 0; i < H; ++i) {
            for (int j = 0; j < W; ++j) {
                if (i > 0) chmin(dp[i][j], dp[i-1][j] + C);
                if (j > 0) chmin(dp[i][j], dp[i][j-1] + C);
                chmin(res, dp[i][j] + A[i][j]);
                chmin(dp[i][j], A[i][j]);
            }
        }
        
        // reverse A
        for (int i = 0; i < H; ++i) reverse(A[i].begin(), A[i].end());
    }
    cout << res << endl;
}