俄罗斯方块游戏

俄罗斯方块游戏

1. 题目描述

你正在玩一个简化版的俄罗斯方块游戏。在这个游戏中，只有一个形状的方块会不断从屏幕顶部下落，这个方块是一个n x n的正方形矩阵（n是一个正整数）。当方块下落到底部或碰到已经堆积的方块时，它会停止下落并固定在那里。

你的任务是判断在给定的方块序列下，这些方块能否在不超出屏幕范围的情况下全部堆积起来。屏幕是一个m x m的正方形区域（m是一个正整数），初始时为空。

输入：

两个整数m和n，分别表示屏幕的大小和每个方块的大小。 一个二维整数数组blocks，表示下落的方块序列。每个方块用一个n x n的矩阵表示，矩阵中的元素为0或1，1表示方块的一部分，0表示空白。

输出：

一个布尔值，表示所有方块能否在不超出屏幕范围的情况下全部堆积起来。能则返回true，否则返回false。

样例输入：

m = 4;
n = 2;
blocks = {
    {
        {1, 1},
        {1, 1}
    },
    {
        {1, 1},
        {0, 1}
    }
}

样例输出：

true

2. 分析

屏幕大小为4x4，方块大小为2x2。第一个方块是一个完整的2x2正方形，它可以放在屏幕的左上角。第二个方块是一个不完整的2x2形状，它也可以放在第一个方块之上，不会超出屏幕范围。这个问题可以通过模拟方块的下落和堆积过程来解决。我们需要一个二维数组来表示屏幕，以及一个函数来检查方块是否能够放置在当前屏幕上。

3. 代码

#include <iostream>
#include <vector>

using namespace std;

bool canPlaceBlock(vector<vector<int>>& screen, vector<vector<int>>& block, int row, int col) {
    int n = block.size();
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (block[i][j] == 1 && (row + i >= screen.size() || col + j >= screen[0].size() || screen[row + i][col + j] == 1)) {
                return false;
            }
        }
    }
    return true;
}

void placeBlock(vector<vector<int>>& screen, vector<vector<int>>& block, int row, int col) {
    int n = block.size();
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (block[i][j] == 1) {
                screen[row + i][col + j] = 1;
            }
        }
    }
}

bool canStackBlocks(int m, int n, vector<vector<vector<int>>>& blocks) {
    vector<vector<int>> screen(m, vector<int>(m, 0));
    int currentRow = 0;

    for (const auto& block : blocks) {
        bool placed = false;
        for (int col = 0; col <= m - n; ++col) {
            if (canPlaceBlock(screen, block, currentRow, col)) {
                placeBlock(screen, block, currentRow, col);
                placed = true;
                currentRow += n; // Move to the next row after placing the block
                break;
            }
        }
        if (!placed) {
            return false; // If we cannot place the block, return false
        }
        if (currentRow >= m) {
            return false; // If the blocks exceed the screen height, return false
        }
    }
    return true;
}

int main() {
    int m = 4;
    int n = 2;
    vector<vector<vector<int>>> blocks = {
        {
            {1, 1},
            {1, 1}
        },
        {
            {1, 1},
            {0, 1}
        }
    };

    cout << (canStackBlocks(m, n, blocks) ? "true" : "false") << endl; // Output should be "true"
    return 0;
}