原题链接

一句话总结：四个关键点是“支架”。

首先注意到右下角的 $n \times n$ 区域内的雪必须全部清除，否则连目的地都不安全，一定会有人生病。

于是我们只需要在左下和右上两块区域中设法开出一条路来。

注意到有八个点，一旦清扫完成就不需要清扫别的点。这些点是 $(n+1, 1), (n+1, n), (2n, 1), (2n, n), (1, n+1), (1, 2n), (n, n+1), (n, 2n)$。感性理解一下。

事实上，只需要在这些点中取最小代价，就得到了最优答案。

因为任何一种合法答案，都必然包含这八个点中的一个。

回到开头的省流，四个关键点是 $(1, 1), (1, n), (n, 1), (n, n)$。

直观上理解，它们不能全都走别的点的路径离开，必须有一个有属于自己的路。或者说，它们支撑了整个网格的结构，如果不移走其中一个的话就动弹不得。

具体的，我们最终肯定需要挪动这四个点到右下角。那么考虑第一次操作它们所在的任意行列。不可能在不使这四个点都不超出左上角 $n \times n$ 区域的情况下进行一次操作。

那么至少有一个点要移动到有雪的区域，我们需要清理它的落点。这落点一共可能有八个，就是上面列出的那些。

所以必然清理这八个点中的至少一个。同时，清理其中任意一个都足够了，不需要额外清理其他点。所以这八个点的代价取 $\min$ 就是答案。

代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

#include <bits/stdc++.h>

using namespace std;
int t;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> t;
    for (int _ = 0; _ < t; ++_) {
        int n;
        cin >> n;

        int64_t term1 = 0;
        vector c(2 * n + 1, vector<int64_t>(2 * n + 1));

        for (int i = 1; i <= 2 * n; ++i) {
            for (int j = 1; j <= 2 * n; ++j) {
                cin >> c[i][j];
                if (i > n && j > n) {
                    term1 += c[i][j];
                }
            }
        }

        int64_t term2 = c[1][n + 1];
        term2 = min(term2, c[1][2 * n]);
        term2 = min(term2, c[n][n + 1]);
        term2 = min(term2, c[n][2 * n]);

        term2 = min(term2, c[n + 1][1]);
        term2 = min(term2, c[n + 1][n]);
        term2 = min(term2, c[2 * n][1]);
        term2 = min(term2, c[2 * n][n]);

        cout << term1 + term2 << '\n';
    }
    return 0;
}