首先，我们要把朋友们安全地移动到右下角 \(n ^ 2\) 个格子，那么铲去这 \(n ^ 2\) 个格子的积雪所花费的代价是无法避免的。然后我们考虑把朋友们移动到这些格子的路程当中所花费的代价该如何最小。我们可以发现，只要有一个朋友到达右下角 \(n ^ 2\) 个格子之一，剩下的朋友可以沿着第一个到达的小朋友所走的路径到达。那么问题就转化为一个朋友从左上角 \(n ^ 2\) 个格子中任意一个格子出发，到达右下角 \(n ^ 2\) 个格子中的任意一个格子的最小花费。可以发现这个朋友只能从右上角初始格子的四个顶点出发，不然答案会变劣。我们就可以分别讨论他要前往哪一个格子。
让我们来讨论一下：
- 从坐标为 \((1, 1)\) 的格子出发
- 向左走一步到达格子 \((1, 2n)\)，再向上走一步到达格子 \((2n, 2n)\)。
- 向上走一步到达格子 \((2n, 1)\)，再向左走一步到达格子 \((2n, 2n)\)。
- 从坐标为 \((1, n)\) 的格子出发
- 向右走一步到达格子 \((1 , n + 1)\)，再向上走一步到达格子 \((2n, n + 1)\)。
- 向上走一步到达格子 \((2n, n)\)，再向右走一步到达格子 \((2n, n + 1)\)。
- 从坐标为 \((n, 1)\) 的格子出发
- 向左走一步到达格子 \((n, 2n)\)，再向下走一步到达格子 \((n + 1, 2n)\)。
- 向下走一步到达格子 \((n + 1, 1)\)，再向右走一步到达格子 \((n + 1, 2n)\)。
- 从坐标为 \((n, n)\) 的格子出发
- 向右走一步到达格子 \((n, n + 1)\)，再向下走一步到达格子 \((n + 1, n + 1)\)。
- 向下走一步到达格子 \((n + 1, n)\)，再向右走一步到达格子 \((n + 1, n + 1)\)。
所以，我们只需计算以上 \(8\) 种情况的花费，然后取最小值即可。相当于对格子 \((1, 2n)\)、格子 \((2n, 1)\)、格子 \((1 , n + 1)\)、格子 \((2n, n)\)、格子 \((n, 2n)\)、格子 \((n + 1, 1)\)、格子 \((n, n + 1)\) 和格子 \((n + 1, n)\) 取最小值。然后再加上清理右下角 \(n ^ 2\) 个格子的积雪的花费即可。
接下来是代码环节：
#include<bits/stdc++.h>
#define int long long
using namespace std;
int t, n, c[505][505], sum;
signed main() {ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin >> t;while (t --) {sum = 0;cin >> n;for (int i = 1; i <= n * 2; i ++) {for (int j = 1; j <= n * 2; j ++) {cin >> c[i][j];}}for (int i = n + 1; i <= n * 2; i ++) {for (int j = n + 1; j <= n * 2; j ++) {sum += c[i][j];}}sum += min(c[1][n + 1], min(c[1][n * 2], min(c[n + 1][1], min(c[n * 2][1], min(c[n][n + 1], min(c[n][n * 2], min(c[n * 2][n], c[n + 1][n])))))));cout << sum << "\n";}return 0;
}