【俄罗斯方块】
- C语言实现
- C++实现
- Java实现
- Python实现
|
💐The Begin💐点点关注，收藏不迷路💐
|
首先把经典的俄罗斯方块简化一下：方块有顺序地从屏幕顶端掉下至底部，当碰到障碍物或底部时停下，同时变成新的障碍物。游戏规则规定，只能在方块下落停止前决定下落时的横向位置，使这个方块编程障碍物后的高度最低，且如果有集中横向位置是这个方块编程障碍物后高度最低时，取最左边的横向位置下落。
输入
第1行有2个整数，表示方块数n和屏幕宽度w，之间用1个空格分隔。
第2行至地i+1行，每行一个整数，为第i个方块的变长为a。
输出
输出一个整数，表示最后障碍物的最高点高度。
样例输入
3 5
2
1
3
样例输出
4
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💐点点关注，收藏不迷路💐
|
