| [Home|Training|Problems|Contests|C Language] | [Login|Register] |
|
Problems Status Rank Statistics |
Problem D
俄罗斯方块2
Time Limit: 2000ms
Memory Limit: 65536kb Description
ZRY在一个宽度为n的游戏池里玩一种叫俄罗斯方块2的游戏。共有7种方块如下图，从左到右编号为0-6.  每次系统会给出7种方块中的一种，你可以对其进行水平右移或顺时针旋转，下图是这几种方块的顺时针旋转示意图。  移动完毕后，方块将垂直落下直到遇到游戏池的底部或者其他方块。 游戏规定游戏池中方块堆起的最高高度为h，所以ZRY要保证方块落下后总高度不能高于h。 这个游戏还有一个规定就是不允许出现方块悬空的情况，即若一个格子是空的，则这个格子的上方不允许出现方块（当然不包括未落下的方块）（这个规定也是俄罗斯方块2与俄罗斯方块的最大区别～）。 若一行被方块占满，则次行会被消除。 在一个方块落下后，系统会产生下一个方块。 ZRY很懒，他希望每次产生一个方块后，总是以最少的平移次数完成下落。如果存在多种方案，则选取顺时针旋转次数最少的方案。 注意，消去是方块落下后形成，故在消去一行之前，也必须满足不悬空与总高度不超过h的规定。  Input
第一行一个整数T，代表数据组数。对于每组数据，第一行为三个整数，n，m，h。分别为游戏池宽度、系统产生的方块数、游戏中最高允许的高度。(1 ≤ n, m , h ≤ 100000) 接下来n行,每行一个整数bi（0 ≤ bi ≤ h),表示当前游戏池中第i列已有的方块数。（数据保证游戏池里方块总数不超过1000000）。 接下来m行，每行一个0-6的整数，表示一个方块。 Output
对于每组数据输出m行，第i行表示第i个方块所需最小平移的次数。数据保证有解。
Sample Input
1 4 3 5 2 0 2 0 1 0 6 Sample Output
0 0 3 Hint
方块从无穷高的最左端落下,旋转的参照点是包含这个方块的最小矩形的左上角那个点.即要保证旋转之后矩形的左上角点在同一个位置.
本题FB奖: 白书一本.
Source
cjy
|