[Login|Register]
Problems

Status

Rank

Problem 1420
俄罗斯方块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
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 1.2ms with 1 query(s).