YeungYeah 的乱写地

CCF201604-2 俄罗斯方块

 Posts  

Problem

问题描述

　　俄罗斯方块是俄罗斯人阿列克谢·帕基特诺夫发明的一款休闲游戏。
　　游戏在一个15行10列的方格图上进行，方格图上的每一个格子可能已经放置了方块，或者没有放置方块。每一轮，都会有一个新的由4个小方块组成的板块从方格图的上方落下，玩家可以操作板块左右移动放到合适的位置，当板块中某一个方块的下边缘与方格图上的方块上边缘重合或者达到下边界时，板块不再移动，如果此时方格图的某一行全放满了方块，则该行被消除并得分。
　　在这个问题中，你需要写一个程序来模拟板块下落，你不需要处理玩家的操作，也不需要处理消行和得分。
　　具体的，给定一个初始的方格图，以及一个板块的形状和它下落的初始位置，你要给出最终的方格图。

输入格式

　　输入的前15行包含初始的方格图，每行包含10个数字，相邻的数字用空格分隔。如果一个数字是0，表示对应的方格中没有方块，如果数字是1，则表示初始的时候有方块。输入保证前4行中的数字都是0。
　　输入的第16至第19行包含新加入的板块的形状，每行包含4个数字，组成了板块图案，同样0表示没方块，1表示有方块。输入保证板块的图案中正好包含4个方块，且4个方块是连在一起的（准确的说，4个方块是四连通的，即给定的板块是俄罗斯方块的标准板块）。
　　第20行包含一个1到7之间的整数，表示板块图案最左边开始的时候是在方格图的哪一列中。注意，这里的板块图案指的是16至19行所输入的板块图案，如果板块图案的最左边一列全是0，则它的左边和实际所表示的板块的左边是不一致的（见样例）

输出格式

　　输出15行，每行10个数字，相邻的数字之间用一个空格分隔，表示板块下落后的方格图。注意，你不需要处理最终的消行。

样例输入

0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 1 0 0 0
1 1 1 0 0 0 1 1 1 1
0 0 0 0 1 0 0 0 0 0
0 0 0 0
0 1 1 1
0 0 0 1
0 0 0 0
3

样例输出

0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 1 0 0 0
1 1 1 1 1 1 1 1 1 1
0 0 0 0 1 1 0 0 0 0

Solution

该问题是一题较为常见的模拟题，需要我们模拟方块的下落情况。就难度而言，并不困难，但相对于其为第二道题的顺序，则稍显得有些麻烦。

具体思路为：读取输入构造方格图，找到下落方块的位置，逐行下降，直至其无法下降为止。思路其实很简单，其核心在于，如何判断方块是否能继续下降，实现了这判断方法，就比较简单了。在这里，我是通过检测下落方块与方块图对于区域是否有重合判断，我将方块图对应位置矩阵与下落方块图相加，若有一元素为2，则出现碰撞，无法下落而结束。具体代码如下

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

m,n = 15,10
board = []
#读取输入构建方格图
for _ in range(m):
    board.append(list(map(int,input().split()[:n])))
#最方格图最下面加一行防止溢出
board.append([1 for _ in range(10)])
#读取下落方块
new = []
for _ in range(4):
    new.append(list(map(int,input().split()[:4])))

pos = int(input())
pos-=1#为什么要减1？第pos行的实际下标为pos-1

#删除下落方格中空行
i = 0
while i <len(new):    
    if sum(new[i])==0:del new[i]
    else:i+=1

new_m = len(new)

new_n = 4

ans = 0
for i in range(15):
    temp = [board[j][pos:pos+new_n] for j in range(i,i+new_m)]
    sumup = [[temp[i][j]+new[i][j] for j in range(new_n)] for i in range(new_m)]
    collsion = False
    for j in range(new_m):
        for k in range(new_n):
            if sumup[j][k]==2:
                collsion=True
                break
        if collsion:break
    if collsion:
        break
    else:ans = i

for i in range(new_m):
    for j in range(new_n):
        if new[i][j]==1:board[ans+i][pos+j]=1

for i in board[:-1]:
    print(' '.join(map(str,i)))

该代码提交后正确，获得了100分。

Reflect

  • 方法上：
    • 在检测能否下落的方法上，其实没有必要从这个对应的矩阵上来判断，可以找出下落方块中为1的点，每次下落只检测这些点在方格图上对应坐标点是否为1。后者在开发效率，运行效率上都更佳。而矩阵相加的方法，直观上实现似乎也很简单，但事实上，原生python对于矩阵运算（即二维数组处理）并没有很好的支持，我一开始觉得实现简单大概是因为此前写了一点Octave，这个语言与python语法有点相近，且完美支持矩阵运算，被影响到了。
  • 解题过程上：这道题作为CCF认证的第二道题，按理来说，是水题，应该快速解决，而实际上，这道题也没有很难，没有涉及到复杂的算法，规模也不大，但是，我却用了一个多小时，而且还没AC，有点可笑，如果是真实的考试中，已经凉了。究其原因，主要有以下几点：
    1. 未考虑清楚就动手写代码。虽然一直对自己强调要想好再开始写代码，但实际上，当有时没什么头绪，或者想得不是太清楚的时候，就会着急写代码，美其名曰先把不需要想的写了，然后边写边想，加快解题速度，但这样却很容易影响思考，让人想不太清楚，并且会被已写的代码影响后续的思考。像这一道题，核心应该是下落过程中能否下落/有无碰撞，但我一开始还没想到方法时，先去实现了一些无关紧要的事，如下落方块中空行空列的删除，并且因为这些事卡住了一段时间，更为好笑的是空列删除还是不必要的。
    2. 一条路上走到黑。在想到的方法实现/运行上出现问题时，我选择的是修复/调试实现代码，而从未去思考过是修改/更换方法，当然其实两种方法都没什么问题，但有时候，因为方法未思考清楚，或者实现起来难度或效果跟预想有偏差，继续在该方法待下去有点浪费时间，就像本题中的碰撞检测所采用的矩阵相加方法来判断，在python原生实现并没有想象中简便。
    3. 读题/题意理解。最后之所以不能AC，即使在本机测试样例能够正确运行，提交后却只有十分，百思不得其解，翻了很多其他人的代码，才发现我对于题意的理解出了偏差。输入的下落位置，表示的应该是整个下落方块最左边（含空列）在第几列（从1开始），而我的理解是，实际方块（不含空列）下落位置在第几列（从0开始），感觉题干说得有点不太清楚，而且唯一的测试样例还有二义性，对于两种解释都符合。在发现了这一点之后再重新看题，似乎在输入上也有点提示，输入在1-7之间，如果是从0开始计数，岂不是无法移到最左面，当然这也是马后炮了，实在可惜。

相关文章：