俄罗斯方块采蘑菇 - 最大价值之和

题目描述

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

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

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

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

输入格式

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

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

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #1

11

写出一个正确的C++代码内容：```cpp #include #include using namespace std;

int n; vector<vector> grid; vector<vector> visited;

// 定义4种阵型的相对坐标 vector<vector<pair<int, int>>> patterns = { {{0, 0}, {0, 1}, {0, 2}, {0, 3}}, {{0, 0}, {1, 0}, {2, 0}, {3, 0}}, {{0, 0}, {0, 1}, {1, 0}, {1, 1}}, {{0, 0}, {0, 1}, {1, 1}, {1, 2}} };

// 判断坐标是否在草地内 bool isValid(int x, int y) { return x >= 0 && x < n && y >= 0 && y < n; }

// 判断是否可以放置阵型 bool canPlace(int x, int y, int patternIndex) { for (auto p : patterns[patternIndex]) { int nx = x + p.first; int ny = y + p.second; if (!isValid(nx, ny) || visited[nx][ny] || grid[nx][ny] == -1) { return false; } } return true; }

// 递归搜索 int dfs(int x, int y, int patternIndex) { if (patternIndex == 4) { return 0; }

int res = 0;

// 尝试放置阵型
if (canPlace(x, y, patternIndex)) {
    for (auto p : patterns[patternIndex]) {
        int nx = x + p.first;
        int ny = y + p.second;
        visited[nx][ny] = 1;
        res += grid[nx][ny];
    }
    
    int nextX = x;
    int nextY = y + 1;
    if (nextY == n) {
        nextX += 1;
        nextY = 0;
    }
    
    // 继续递归搜索下一个阵型
    res += dfs(nextX, nextY, patternIndex + 1);
    
    // 回溯
    for (auto p : patterns[patternIndex]) {
        int nx = x + p.first;
        int ny = y + p.second;
        visited[nx][ny] = 0;
        res -= grid[nx][ny];
    }
}

// 不放置阵型，继续搜索下一个位置
int nextX = x;
int nextY = y + 1;
if (nextY == n) {
    nextX += 1;
    nextY = 0;
}
res = max(res, dfs(nextX, nextY, patternIndex));

return res;

}

int main() { cin >> n;

grid.resize(n, vector<int>(n));
visited.resize(n, vector<int>(n));

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        cin >> grid[i][j];
    }
}

int res = dfs(0, 0, 0);
cout << res << endl;

return 0;

}