【俄罗斯方块】

🕗 发布于 2024-11-20 09:45 算法 C语言 C++

【俄罗斯方块】

💐The Begin💐点点关注，收藏不迷路💐

首先把经典的俄罗斯方块简化一下：方块有顺序地从屏幕顶端掉下至底部，当碰到障碍物或底部时停下，同时变成新的障碍物。游戏规则规定，只能在方块下落停止前决定下落时的横向位置，使这个方块编程障碍物后的高度最低，且如果有集中横向位置是这个方块编程障碍物后高度最低时，取最左边的横向位置下落。

输入

第1行有2个整数，表示方块数n和屏幕宽度w，之间用1个空格分隔。
第2行至地i+1行，每行一个整数，为第i个方块的变长为a。

输出

输出一个整数，表示最后障碍物的最高点高度。

样例输入

样例输出

C语言实现

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

// 定义一个较大的数，用于表示无穷大的概念
#define INF 100000

// 计算俄罗斯方块游戏结束后障碍物的最高点高度
int russianBlocks(int n, int w, int blocks[]) {
    int h[2010];  // 用于存储每一列的高度，假设屏幕宽度最大为2010，可根据实际情况调整
    int maxx = 0;

    // 初始化每一列的高度为0
    for (int i = 0; i < w; i++) {
        h[i] = 0;
    }

    // 遍历每个方块
    for (int i = 0; i < n; i++) {
        int a = blocks[i];
        int minn = INF;  // 初始化最小高度为一个较大的值
        int mi = 0;  // 用于记录使得放置方块后高度最低的起始列索引

        // 遍历每一个可能放置方块的起始位置
        for (int j = 0; j < w - a + 1; j++) {
            int max = 0;

            // 检查在当前起始位置放置方块所覆盖列中的最大高度
            for (int k = j; k <= j + a - 1; k++) {
                if (h[k] > max) {
                    max = h[k];
                }
            }

            // 如果当前位置放置方块后的最大高度比之前记录的最小高度还小，更新最小高度和对应的索引
            if (max < minn) {
                minn = max;
                mi = j;
            }
        }

        // 在找到的最佳位置放置方块，更新对应列的高度
        for (int j = mi; j <= mi + a - 1; j++) {
            h[j] = minn + a;
        }
    }

    // 找到所有列高度中的最大值，即障碍物的最高点高度
    for (int i = 0; i < w; i++) {
        if (h[i] > maxx) {
            maxx = h[i];
        }
    }

    return maxx;
}

int main() {
    int n, w;
    int blocks[1000];  // 假设方块数量最多为1000个，可根据实际情况调整

    // 读取方块数量和屏幕宽度
    scanf("%d %d", &n, &w);

    // 读取每个方块的边长
    for (int i = 0; i < n; i++) {
        scanf("%d", &blocks[i]);
    }

    // 调用函数计算并输出最后障碍物的最高点高度
    printf("%d\n", russianBlocks(n, w, blocks));

    return 0;
}

C++实现

#include <iostream>
#include <algorithm>
#include <cstring>

// 定义一个较大的数，用于表示无穷大的概念
const int INF = 100000;

// 计算俄罗斯方块游戏结束后障碍物的最高点高度
int russianBlocks(int n, int w, const int blocks[]) {
    int h[2010];  // 用于存储每一列的高度，假设屏幕宽度最大为2010，可根据实际情况调整
    int maxx = 0;

    // 初始化每一列的高度为0
    std::fill_n(h, w, 0);

    // 遍历每个方块
    for (int i = 0; i < n; i++) {
        int a = blocks[i];
        int minn = INF;  // 初始化最小高度为一个较大的值
        int mi = 0;  // 用于记录使得放置方块后高度最低的起始列索引

        // 遍历每一个可能放置方块的起始位置
        for (int j = 0; j < w - a + 1; j++) {
            int max = 0;

            // 检查在当前起始位置放置方块所覆盖列中的最大高度
            for (int k = j; k <= j + a - 1; k++) {
                if (h[k] > max) {
                    max = h[k];
                }
            }

            // 如果当前位置放置方块后的最大高度比之前记录的最小高度还小，更新最小高度和对应的索引
            if (max < minn) {
                minn = max;
                mi = j;
            }
        }

        // 在找到的最佳位置放置方块，更新对应列的高度
        for (int j = mi; j <= mi + a - 1; j++) {
            h[j] = minn + a;
        }
    }

    // 找到所有列高度中的最大值，即障碍物的最高点高度
    for (int i = 0; i < w; i++) {
        if (h[i] > maxx) {
            maxx = h[i];
        }
    }

    return maxx;
}

int main() {
    int n, w;
    int blocks[1000];  // 假设方块数量最多为1000个，可根据实际情况调整

    // 读取方块数量和屏幕宽度
    std::cin >> n >> w;

    // 读取每个方块的边长
    for (int i = 0; i < n; i++) {
        std::cin >> blocks[i];
    }

    // 调用函数计算并输出最后障碍物的最高点高度
    std::cout << russianBlocks(n, w, blocks) << std::endl;

    return 0;
}

Java实现

import java.util.Scanner;

// 计算俄罗斯方块游戏结束后障碍物的最高点高度
public class Main {

    // 定义一个较大的数，用于表示无穷大的概念
    public static final int INF = 100000;

    public static int russianBlocks(int n, int w, int[] blocks) {
        int[] h = new int[2010];  // 用于存储每一列的高度，假设屏幕宽度最大为2010，可根据实际情况调整
        int maxx = 0;

        // 初始化每一列的高度为0
        for (int i = 0; i < w; i++) {
            h[i] = 0;
        }

        // 遍历每个方块
        for (int i = 0; i < n; i++) {
            int a = blocks[i];
            int minn = INF;  // 初始化最小高度为一个较大的值
            int mi = 0;  // 用于记录使得放置方块后高度最低的起始列索引

            // 遍历每一个可能放置方块的起始位置
            for (int j = 0; j < w - a + 1; j++) {
                int max = 0;

                // 检查在当前起始位置放置方块所覆盖列中的最大高度
                for (int k = j; k <= j + a - 1; k++) {
                    if (h[k] > max) {
                    max = h[k];
                    }
                }

                // 如果当前位置放置方块后的最大高度比之前记录的最小高度还小，更新最小高度和对应的索引
                if (max < minn) {
                    minn = max;
                    mi = j;
                }
            }

            // 在找到的最佳位置放置方块，更新对应列的高度
            for (int j = mi; j <= mi + a - 1; j++) {
                h[j] = minn + a;
            }
        }

        // 找到所有列高度中的最大值，即障碍物的最高点高度
        for (int i = 0; i < w; i = i + 1) {
            if (h[i] > maxx) {
                maxx = h[i];
            }
        }

        return maxx;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int w = scanner.nextInt();

        int[] blocks = new int[n];

        // 读取每个方块的边长
        for (int i = 0; i < n; i++) {
            blocks[i] = scanner.nextInt();
        }

        // 调用函数计算并输出最后障碍物的最高点高度
        System.out.println(russianBlocks(n, w, blocks));

        scanner.close();
    }
}

Python实现

def russian_blocks(n, w, blocks):
    h = [0] * w  # 用于存储每一列的高度
    maxx = 0

    # 遍历每个方块
    for i in range(n):
        a = blocks[i]
        minn = 100000  # 初始化最小高度为一个较大的值
        mi = 0  # 用于记录使得放置方块后高度最低的起始列索引

        # 遍历每一个可能放置方块的起始位置
        for j in range(w - a + 1):
            max_value = 0

            # 检查在当前起始位置放置方块所覆盖列中的最大高度
            for k in range(j, j + a):
                if h[k] > max_value:
                    max_value = h[k]

            # 如果当前位置放置方块后的最大高度比之前记录的最小高度还小，更新最小高度和对应的索引
            if max_value < minn:
                minn = max_value
                mi = j

        # 在找到的最佳位置放置方块，更新对应列的高度
        for j in range(mi, mi + a):
            h[j] = minn + a

    # 找到所有列高度中的最大值，即障碍物的最高点高度
    for i in range(w):
        if h[i] > maxx:
            maxx = h[i]

    return maxx


n, w = map(int, input().split())
blocks = [int(input()) for i in range(n)]

# 调用函数计算并输出最后障碍物的最高点高度
print(russian_blocks(n, w, blocks))

在这里插入图片描述

💐The End💐点点关注，收藏不迷路💐

原文地址：https://blog.csdn.net/qq_41840843/article/details/143274186

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：VB.Net笔记-更新ing
下一篇：Linux线程（整理）

论文阅读——Intrusion detection systems using longshort‑term memory (LSTM)
作者提出的 LSTM 模型能够有效区分正常网络流量和攻击流量。除此之外，模型结合主成分分析（PCA）和互信息作为降维方法。实验结果表明，基于 PCA 的模型（特别是使用2个主成分）在二分类和多分类任务
阅读更多2024-11-21
用源码编译虚幻引擎，并打包到安卓平台
本文详细介绍了如何用源码编译虚幻引擎，并将其打包到安卓平台。
阅读更多2024-11-21
Vue项目开发 element-UI 前端实现 1到10排列选择的按钮
在 Element UI 中，你可以通过来实现按钮的排列选择，例如让用户选择 1 到 10 之间的数字。为了实现这一功能，我们可以使用来动态生成 1 到 10 的按钮，并通过按钮点击事件来更新
阅读更多2024-11-21
Java EE 【知识改变命运】01计算机的一些知识点
计算机一些基础知识
阅读更多2024-11-21
04 —— Webpack打包CSS代码
加载器style-loader：把解析后的css代码插入到DOM。加载器css-loader ：解析css代码。直接引用，不用变量接收。
阅读更多2024-11-21
万能程序补丁工具 C# 源代码详解
万能程序补丁工具程序目的：搜索二进制可执行 EXE 或 DLL 文件分析的特征代码，替换特征代码，达到调试修正目标程序的功能。
阅读更多2024-11-21
【MySQL数据库】C#实现MySQL数据库最简单的查询和执行函数
C#和MySQL数据库是常见的数据交互，标准的查询和执行方法如下，做个记录。
阅读更多2024-11-21
单条推理转批量推理prompt
在每个线程中设置环境变量 CUDA_VISIBLE_DEVICES，以确保每个线程只使用指定的GPU。使用 concurrent.futures.ThreadPoolExecutor 来管理多线程任务
阅读更多2024-11-21
【AIGC】ChatGPT提示词Prompt解析：情感分析，分手后还可以做朋友吗？
【AIGC】在情感博弈中，最重要的是保持清醒的认知和优雅的态度。识别控制话术不是为了对抗，而是为了更好地保护自己的情感自由，实现真正的成长。
阅读更多2024-11-21
pycharm中配置pyqt5
PyQt和wxPython则提供了更多的控件和更强大的功能，适合于需要复杂用户界面的应用程序。pyQt生成的应用程序，引用图片通常是将资源文件装换为 python 文件，然后引用资源文件，而不能直接加
阅读更多2024-11-21

【俄罗斯方块】

【俄罗斯方块】

C语言实现

C++实现

Java实现

Python实现

相关文章