俄罗斯方块采蘑菇：算法与代码实现

题目描述

有一块 $n \times n$ 的草地，每个单位块的草地上长着一个蘑菇，位于 $(i,j)$ 位置的蘑菇的价值是 $a_{ij}$，如果 $a_{ij} \ge 0$，说明这是一个可以采集的蘑菇；如果 $a_{ij} = -1$，说明这是一个毒蘑菇。

有 $4$ 位俄罗斯小矮人去采蘑菇，他们必须排列成某种特殊的阵型才能够采蘑菇，并且他们不能采集到毒蘑菇。 阵型包括以下图中所示的 $1$ 种（编号 $1$）：

每种阵型都可以任意旋转，旋转过后的阵型仍然是符合要求、可以采集蘑菇的。每种阵型最多只能采集 $1$ 次。

求在给定草地上，用这种阵型去采蘑菇，能够采集到的最大价值之和是多少。

输入格式

第一行输入一个正整数 $n$（$4 \le n \le 100$）。

接下来 $n$ 行，每行输入 $n$ 个正整数 $a_{ij}$（$-1 \le a_{ij} \le 100$），构成一个代表草地的矩阵。

输出格式

输出一行 $1$ 个整数，代表用 $1$ 号阵型采集蘑菇的最大价值之和。如果无法采集到蘑菇，输出 $0$。

样例 #1

样例输入 #1

4
1 2 3 2
3 -1 2 1
4 0 1 2
3 2 1 -1

样例输出 #1

11

代码实现

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;
    
    vector<vector<int>> grass(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> grass[i][j];
        }
    }
    
    int maxSum = 0;
    for (int i = 0; i <= n - 4; i++) {
        for (int j = 0; j <= n - 4; j++) {
            int sum = 0;
            sum += grass[i][j] + grass[i][j+1] + grass[i][j+2] + grass[i][j+3];
            sum += grass[i+1][j] + grass[i+1][j+1] + grass[i+1][j+2] + grass[i+1][j+3];
            sum += grass[i+2][j] + grass[i+2][j+1] + grass[i+2][j+2] + grass[i+2][j+3];
            sum += grass[i+3][j] + grass[i+3][j+1] + grass[i+3][j+2] + grass[i+3][j+3];
            
            maxSum = max(maxSum, sum);
        }
    }
    
    cout << maxSum << endl;
    
    return 0;
}