테트리스

테트리스

 

제한시간: 1000 ms    메모리제한: 256 MB

 

3 * 3 크기의 2차원 테이블에 일부 테트리스 유형뿐만 아니라 

아래 그림과 같이 하나 이상의 셀이 채워진 블록이 주어진다.

 

 

이 블록을 쌓아갈때 가로줄이 모두 채워지면 그 가로줄은 삭제된다.

주어진 모든 블록을 쌓은 후 최종적으로 남은 블록중 최대 높이를 구하는 프로그램을 작성하시오.

블록 정보에서 채워진 곳은 1, 비어있는 곳은 0으로 표시된다.

 

첫 번째 줄에 테트리스의 가로줄의 크기 N과 블록의 개수 M이 주어진다. (3 <= N <= 20, 5 <= M <= 10000) 다음 줄부터 M줄에 걸쳐 블록의 정보와 회전수 R( 0 <= R <= 1,000) 및 이동 수 S( 0 <= S <= 1,000)가 입력된다. 블록의 정보는 0과 1로 이루어진 9개의 정수로 표시되며 3개씩 묶어서 한 행을 나타낸다. 회전수는 시계방향으로 90도씩 회전하는 횟수를 의미한다. 초기 위치는 회전수만큼 회전을 끝낸 후 좌표에서 블록을 왼쪽 벽에 붙인 상태에서 오른쪽으로 이동하는 횟수를 의미한다. 이 때 블록의 왼쪽이 모두 비어 있으면 왼쪽으로 이동하여 1개라도 채워있는 곳을 왼쪽 벽에 붙인 후 오른쪽으로 이동하여야 하며 이동 후 블록의 채워진 값이 오른쪽 벽을 넘어갈 경우에는 오른쪽 벽에 붙인다.

입력되는 블록을 밑으로 떨어뜨려서 가로줄이 채워지면 해당 줄을 모두 제거하는 작업을 반복한 후 최대 높이를 출력한다.

 

10 10

1 1 1 0 1 0 0 1 0 2 0

1 0 0 1 0 0 1 0 0 1 4

0 1 0 1 1 1 0 1 0 2 2

1 0 0 1 0 0 1 0 0 0 9

1 1 0 0 1 0 0 1 1 2 6

1 1 1 0 0 1 0 0 1 0 6

1 0 0 1 0 0 1 0 0 0 5

1 1 1 0 0 1 0 0 1 3 0

1 1 1 0 1 0 0 0 0 1 3

1 0 0 1 0 0 1 0 0 0 9

 

4

 

10 7

0 0 0 1 1 1 0 0 1 0 0

0 0 0 1 1 1 1 1 1 4 3

0 0 0 1 1 0 1 1 0 0 6

1 1 0 1 1 0 1 1 0 0 9

1 0 0 1 1 0 1 1 0 5 0

1 1 1 0 0 0 0 0 0 6 3

1 1 0 0 0 0 0 0 0 2 6

 

0

 

  

입력예1에 따라 차례대로 떨어뜨린 모양

 

#include <stdio.h>

int N, M, H, P, tet[30010], gogo[3]; // 테트리스판을 비트로 표현함, gogo는 하나의 블록을 압축함

void rotate(int b[3][3])
{
	int a[3][3], i, j;
	for (i = 0; i < 3; i++) for (j = 0; j < 3; j++) { // 회전 시키기 이중 포문으로
		a[i][j] = b[j][2 - i];
	}
	for (i = 0; i < 3; i++) for (j = 0; j < 3; j++) {
		b[i][j] = a[i][j]; // 회전시킨 것 복사하기
	}
}

void input()
{
	int block[3][3], R, S, i, j;
	for (i = 2; i >= 0; i--) for (j = 0; j < 3; j++) scanf("%d", &block[i][j]);
	scanf("%d %d", &R, &S); // 회전수, 이동수
	R %= 4; // 회전 
	if (S > N) S = N; // 오른쪽 벽에 붙었을 때
	while (R--) rotate(block);
	for (i = 0; i < 3; i++) gogo[i] = (block[i][2] << 2) + (block[i][1] << 1) + block[i][0]; // 3x3을 3x1로 나타내기
	while ((gogo[0] & 1) + (gogo[1] & 1) + (gogo[2] & 1) == 0) for (i = 0; i < 3; i++) gogo[i] >>= 1; // 왼쪽 벽이 비어 있으면 이동
	while (gogo[0] == 0) gogo[0] = gogo[1], gogo[1] = gogo[2], gogo[2] = 0; // 칸 내리기
	for (i = 0; i < 3; i++) gogo[i] <<= S; // 칸 이동하기
	while (gogo[0] > P || gogo[1] > P || gogo[2] > P) for (i = 0; i < 3; i++) gogo[i] >>= 1; //오른쪽으로 칸 넘어가면 이동시킴
}

void drop()
{
	int i, j, k; // 변수 활용 ++, -- 이므로 확인 하고 사용
	for (i = H; i > 0; i--) { // 제일 놓은 곳 부터 검사
		if ((tet[i] & gogo[0]) + (tet[i + 1] & gogo[1]) + (tet[i + 2] & gogo[2])) break; // 겹치는게 있으면 드랍안함
	}
	for (++i, j = 0; j < 3; i++, j++) {
		tet[i] += gogo[j]; // 드랍중
		if (tet[i] && i > H) H = i;  // 제일 높은 칸
	}
	for (j = i - 1; j >= i - 3; j--) { 
		if (tet[j] == P) {
			for (k = j; k <= H; k++) tet[k] = tet[k + 1]; // 하나씩 삭제함
			H--;
		}
	}
}

int main()
{
	freopen("input.txt", "r", stdin);
	scanf("%d %d", &N, &M);
	P = (1 << N) - 1;
	while (M--) {
		input();
		drop();
	}
	printf("%d\n", H);
	return 0;
}