codeforces1621D The Winter Hike（思维/贪心）

题目链接：codeforces 1621D

题目思路：

不难得出右下角的所有雪全清，接下来就是找到右上角到右下角的路径。关键是找到到右下角区域的入口。根据移动方式，再贪心只选择一个入口，画图可知只有八个入口，取最小值即可。

参考代码：

#include <iostream>
using namespace std;
typedef long long ll;
const int maxn = 550;
int n;
ll a[maxn][maxn];
void solver() {
   
	ll ans = 0;
    cin >> n;
    for (int i = 1; i <= n * 2; i++) {
   
        for (int j = 1; j <= n * 2; j++) {
   
            cin >> a[i][j];
            if (i >= n+1 && j >= n+1) {
   
                ans += a[i][j];
            }
        }
    }
    ll oth = min(a[1][n+1], min(a[1][2*n], min(a[n][n+1], min(a[n][2*n], min(a[n+1][1], min(a[n+1][n], min(a[2*n][1], a[2*n][n])))))));
    ans += oth;
    cout << ans << '\n';
}
int main() {
   
    int _ = 1;
    cin >> _;
    while (_--) {
   
        solver();
    }
}