テトリス

問題 パソコン甲子園2008 06

テトリスをシミュレーションして下さい。盤面の大きさは横 5 コマで、落ちてくるブロックはすべて直線状で、横向き、縦向きの２種類があり、長さは 1 から 5 までの 5 種類です(全部で10種類)。

いくつかのブロックを落としていき、全てブロックで埋まった横一列は削除され、その列の上にあったブロックたちはそのままの形で下へ落ちます。最後に残るブロックのコマ数を求めて下さい。




出典（パソコン甲子園２００８）

入力例
4
1 4 1
1 3 1
2 2 4
2 3 5
0

出力例
2

解説

２次元配列で盤面を表現することもできますが、ここでは整数型の１次元配列（stack）で盤面を表します。
stack[i] には盤面の下から i 行目のブロック片の状態を記録します。各行のブロック片の状態を整数で表すために、ブロック片の並びをビットとみなします。ブロック片がある状態を 1 ない状態を 0 とします。例えば、ある行のブロック片

■□■■□

は

10110（2進数）

と表されるので、22（10進数）となります。

例えば、盤面が

5□□□■□
4□□□■□
3■□■■■
2■■■□□
1■□■■□

の状態ならば、スタックの中身は

stack = {22, 28, 23, 2, 2}

となります。

このstackに、同様に整数で表されたブロックを落としていきます。
例えば、上記の盤面にブロック

■■■□□

を落とすと

5□□□■□
4■■■■□
3■□■■■
2■■■□□
1■□■■□

となります。
ここで、ブロックが置かれる位置は、ブロックを上から落としたときに、すでにあるブロック片にひっかかる直前の位置です。
この位置は、stack の頂点から下に向かってブロックの値とスタックの値の論理積をとり、論理積が0とならない直前の位置となります。

例えば、今落したブロック
■■■□□
と、stack[5] のブロック片
□□□■□
との論理積（28 & 2）は 0 となるので、すり抜けます。

例えば、ブロック
■■■□□
と、stack[3] のブロック片
■□■■■
との論理積（23 & 2）は 0 とはならないので、このブロック片の上にブロックが置かれます。

ブロックを置いた後に、ブロック片が５つ並んでいる場所、つまり stack の要素が 31 の場所を消していきます。

便宜上、stack[0] を 31 とします。

サンプルプログラム

001 #include<iostream>
002 using namespace std;
003 #define MAX 5000
004 
005 class Tetoris{
006     public:
007     int stack[MAX+1], top;
008     Tetoris(){ stack[0] = 31; top = 0; }
009     
010     void insert( int o, int p, int q ){
011         int value = (o == 1 ? (((2 << p-1)-1) << (q-1)) : (1 << (q-1)));
012         int target = getTarget( value );
013         for ( int i = target;  i < target + ((o == 2) ? p : 1); i++ ){
014             if ( i > top ){
015                 stack[i] = value;
016                 top = i;
017             } else {
018                 stack[i] += value;
019             }
020         }
021         
022         while( erase());
023     }
024     
025     bool erase(){
026         for ( int i = 1; i <= top; i++ ){
027             if ( stack[i] == 31 ){
028                 for ( int j = i+1; j <= top; j++ ) stack[j-1] = stack[j];
029                 top--; return true;
030             }
031         }
032         return false;
033     }
034     
035     int getResult(){
036         int sum = 0;
037         for ( int i = top; i >= 1; i-- ){
038             int val = stack[i];
039             while( val ){
040                 if ( val%2 ) sum++;
041                 val /= 2;
042             }
043         }
044         return sum;
045     }
046     
047     int getTarget( int value ){
048         int target = top;
049         while( (stack[target] & value) == 0 ) target--;
050         return target + 1;
051     }
052 };
053 
054 int main(){
055     int n, o, p, q;
056     while( cin >> n && n ){
057         Tetoris tetoris;
058         for ( int i = 0; i < n; i++ ) {
059             cin >> o >> p >> q;
060             tetoris.insert(o, p, q);
061         }
062         cout << tetoris.getResult() << endl;
063     }
064     return 0;
065 }