スポンサーサイト

--.--.-- --:--  スポンサー広告

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

| - | - | ↑ページトップ |




テトリス

2008.09.15 11:48  パソコン甲子園 2008

問題 パソコン甲子園2008 06

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

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

pck200806_1.gif

pck200806_2.gif
出典(パソコン甲子園2008)


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

出力例
2


解説

2次元配列で盤面を表現することもできますが、ここでは整数型の1次元配列(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 とはならないので、このブロック片の上にブロックが置かれます。

ブロックを置いた後に、ブロック片が5つ並んでいる場所、つまり 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 }




スポンサーサイト

テーマ : プログラミング - ジャンル : コンピュータ

| コメント(2) | トラックバック(0) | ↑ページトップ |

この記事へのコメント

うっかりだと思いますが、論理積とすべきところを倫理和と書いてますよ。

| URL | 2008.09.30 13:53

ご指摘ありがとうございました!。修正しました。

管理者 | URL | 2008.09.30 19:11 | 編集

コメントを書く


管理人にのみ表示

↑ページトップ

この記事へのトラックバック

この記事にトラックバックする(FC2ブログユーザー)

↑ページトップ

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。