Bricks 题解

题目分析

这是一个类似俄罗斯方块的游戏，在一个 $6 \times 8$ 的网格中进行。游戏的关键特性：

• 砖块独立下落，不会形成空洞
• 砖块阵型可以旋转 $0^\circ$、$90^\circ$、$180^\circ$、$270^\circ$
• 每轮结束时，高度 $\geq 3$ 的列会坍塌并计分
• 目标是最化总得分：$\sum_{i=1}^{N} b_i s_i$

解题思路

核心算法：状态压缩动态规划

由于网格只有6列，每列高度在0-8之间，可以将整个游戏状态编码为一个整数：

• 使用9进制数编码6列的高度
• 状态空间大小为 $9^6 = 531441$

关键步骤

1. 预处理旋转：为每个砖块阵型计算4种旋转后的列砖块数
2. 状态转移：对于每个状态，尝试所有可能的放置方式
3. 坍塌处理：检查并移除满足条件的列，计算得分
4. 动态规划优化：使用滚动数组减少内存使用

C语言实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define COLS 6
#define ROWS 8
#define MAX_N 300
#define MAX_STATES 531441  // 9^6
#define INF -1

// 实用函数：返回最大值
int max(int a, int b) {
    return a > b ? a : b;
}

// 旋转结构体：存储旋转后的宽度、高度和各列砖块数
typedef struct {
    int w, h;
    int cols[6];
} Rotation;

// 全局变量
int N;
int w[MAX_N], h[MAX_N], s[MAX_N];
char pattern[MAX_N][10][10];
Rotation rotations[MAX_N][4];

// 动态规划数组（使用滚动数组）
int dp[2][MAX_STATES];
int current = 0, next = 1;

// 将高度数组编码为状态整数
int encode(int *height) {
    int code = 0;
    int base = 1;
    for (int i = 0; i < COLS; i++) {
        code += height[i] * base;
        base *= 9;
    }
    return code;
}

// 将状态整数解码为高度数组
void decode(int code, int *height) {
    for (int i = 0; i < COLS; i++) {
        height[i] = code % 9;
        code /= 9;
    }
}

// 计算字符串中'#'的数量
int count_hash(char *s, int len) {
    int cnt = 0;
    for (int i = 0; i < len; i++) {
        if (s[i] == '#') cnt++;
    }
    return cnt;
}

// 预处理所有砖块阵型的4种旋转
void precompute_rotations() {
    for (int i = 0; i < N; i++) {
        // Rotation 0度（原始）
        rotations[i][0].w = w[i];
        rotations[i][0].h = h[i];
        for (int j = 0; j < w[i]; j++) {
            rotations[i][0].cols[j] = 0;
            for (int k = 0; k < h[i]; k++) {
                if (pattern[i][k][j] == '#') {
                    rotations[i][0].cols[j]++;
                }
            }
        }
        
        // Rotation 90度（逆时针）
        rotations[i][1].w = h[i];
        rotations[i][1].h = w[i];
        for (int j = 0; j < h[i]; j++) {
            rotations[i][1].cols[j] = count_hash(pattern[i][h[i]-1-j], w[i]);
        }
        
        // Rotation 180度
        rotations[i][2].w = w[i];
        rotations[i][2].h = h[i];
        for (int j = 0; j < w[i]; j++) {
            rotations[i][2].cols[j] = 0;
            for (int k = 0; k < h[i]; k++) {
                if (pattern[i][k][w[i]-1-j] == '#') {
                    rotations[i][2].cols[j]++;
                }
            }
        }
        
        // Rotation 270度（顺时针）
        rotations[i][3].w = h[i];
        rotations[i][3].h = w[i];
        for (int j = 0; j < h[i]; j++) {
            rotations[i][3].cols[j] = count_hash(pattern[i][j], w[i]);
        }
    }
}

int main() {
    // 读取输入
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        scanf("%d %d %d", &w[i], &h[i], &s[i]);
        for (int j = 0; j < h[i]; j++) {
            scanf("%s", pattern[i][j]);
        }
    }
    
    // 预处理所有旋转
    precompute_rotations();
    
    // 初始化动态规划数组
    for (int i = 0; i < MAX_STATES; i++) {
        dp[current][i] = INF;
    }
    dp[current][0] = 0;  // 初始状态：所有列为空
    
    // 动态规划主循环
    for (int round = 0; round < N; round++) {
        // 初始化下一轮状态
        for (int i = 0; i < MAX_STATES; i++) {
            dp[next][i] = INF;
        }
        
        // 遍历所有可能的状态
        for (int state = 0; state < MAX_STATES; state++) {
            if (dp[current][state] == INF) continue;
            
            int height[COLS];
            decode(state, height);
            
            // 尝试所有旋转
            for (int rot = 0; rot < 4; rot++) {
                Rotation *r = &rotations[round][rot];
                
                // 尝试所有水平放置位置
                for (int x = 0; x <= COLS - r->w; x++) {
                    int new_height[COLS];
                    memcpy(new_height, height, sizeof(new_height));
                    
                    // 应用砖块阵型
                    int valid = 1;
                    for (int j = 0; j < r->w; j++) {
                        new_height[x + j] += r->cols[j];
                        // 检查是否超出网格高度
                        if (new_height[x + j] > ROWS) {
                            valid = 0;
                            break;
                        }
                    }
                    if (!valid) continue;
                    
                    // 检查坍塌并计算得分
                    int collapse_score = 0;
                    for (int j = 0; j < COLS; j++) {
                        if (new_height[j] >= 3) {
                            collapse_score += new_height[j];
                            new_height[j] = 0;
                        }
                    }
                    
                    // 编码新状态并更新DP
                    int new_state = encode(new_height);
                    int new_score = dp[current][state] + collapse_score * s[round];
                    
                    if (new_score > dp[next][new_state]) {
                        dp[next][new_state] = new_score;
                    }
                }
            }
        }
        
        // 切换滚动数组
        current = 1 - current;
        next = 1 - next;
    }
    
    // 寻找最大得分
    int answer = 0;
    for (int state = 0; state < MAX_STATES; state++) {
        if (dp[current][state] > answer) {
            answer = dp[current][state];
        }
    }
    
    printf("%d\n", answer);
    return 0;
}

算法详解

1. 状态编码与解码

• 编码：将6列的高度数组转换为0-531440之间的整数
• 解码：将状态整数转换回高度数组
• 使用9进制编码，因为每列高度范围为0-8

2. 旋转预处理

为每个砖块阵型计算4种旋转：

• 0度：原始方向
• 90度：逆时针旋转，统计每行砖块数作为新列
• 180度：上下左右翻转
• 270度：顺时针旋转

3. 动态规划状态转移

对于每个状态：

1. 解码得到当前各列高度
2. 尝试所有旋转和放置位置
3. 计算新高度并检查有效性
4. 处理坍塌并计算得分
5. 更新新状态的得分

4. 坍塌机制

• 检查每列高度是否≥3
• 坍塌列的所有砖块被移除
• 得分 = 坍塌砖块数 × 轮次得分

复杂度分析

• 状态空间：$9^6 = 531441$ 个状态
• 每轮操作：$531441 \times 4 \times 6 \approx 1.3 \times 10^7$ 次操作
• 总复杂度：$O(N \times \text{states} \times \text{rotations} \times \text{positions})$
• 在 $N \leq 300$ 的约束下可行

样例验证

输入

3
2 2 10
#_
##
3 2 4
#_#
_#_
3 3 2
#_#
###
#__

输出

30

该解法通过状态压缩动态规划高效地搜索所有可能的游戏路径，找到最优的砖块放置策略，从而最大化总得分。