22204 - Tiny - 4

문제 번역

테트리스에서 몇가지 조건이 변경되었습니다.

1. 게임 판은 9*9입니다.

2. 블럭은 회전이 불가능하고 떨어지는 동안 움직일 수 없습니다.

3. 블럭은 9 종류가 있습니다.

4. 블럭이 떨어지는 순서가 있을 때 모든 블럭을 다 떨어트려야 합니다.

step 1

이 문제는 지금까지의 문제와 결이 살짝 다릅니다. 게임 판이 주어졌을 때 해당 게임 판이 얼마나 좋은지 점수를 매겨봅시다. 이 점수가 좋은 쪽을 따라가다 보면 게임을 끝낼 수 있습니다.

step 2

3가지 기준을 세웁니다.

1. 비어있는 가로줄 당 20점

2. 블럭을 놓았을 때 제거되는 가로줄 당 90점

3. 빈칸 위에 블럭이 있는 경우 블럭 개수 당 -5점

 

앞으로 올 4개의 블럭을 놓을 수 있는 경우의 수는 $9^4$입니다. 모든 경우에 대해 블럭을 내려보고 가장 점수가 높은 곳으로 떨어트립니다.

코드

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<vector>
#include<queue>
#include<map>
#include<string>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
int b[60000];
int mapp[10][30],tmp[10][30],step[10];
int block[9][3][3],err=0;
int dp[10], ans[60000];
int removeS = 90, height = 20,hard = 5;
int drop(int bl, int po) {
    if (bl == 4 && po >= 7) {
        err = 1;return 0;
    }
    if ((bl == 2 || bl == 5 || bl == 6 || bl == 7 || bl == 8) && po >= 8) {
        err = 1;return 0;
    }
    int i, j, k;
    for (i = 11;i >= 0;i--) {
        int e = 0;
        for (j = 0;j < 3;j++) {
            if(po+j>=9) break;
            for (k = 0;k < 3;k++) {
                if (tmp[po + j][i + k] == 1 && block[bl][j][k] == 1) {
                    e = 1;
                    break;
                }
            }
        }
        if (e == 1) break;
    }
    i++;
    for (j = 0;j < 3;j++) {
        if (po + j >= 9) break;
        for (k = 0;k < 3;k++) {
            if (block[bl][j][k] == 1) tmp[po + j][i + k] = 1;
        }
    }

    for (i = 0;i < 9;i++) {
        if (tmp[i][9] == 1) { err = 1;return 0; }
    }
    int height = 0,cnt=0;
    for (i = 0;i < 9;i++) {
        while (1) {
            int ch = 0;
            for (j = 0;j < 9;j++) {
                if (tmp[j][height] == 0) break;
            }
            if (j == 9) { height++; cnt++; }
            else break;
        }
        for (j = 0;j < 9;j++) tmp[j][i] = tmp[j][height];
        height++;
    }

    return cnt;
}
int calcLoss() {
    int i, j,cnt=0,cnt1=0;
    for (i = 8;i >= 0;i--) {
        for (j = 0;j < 9;j++) {
            if (tmp[j][i] == 1) break;
        }
        if (j != 9) break;
        cnt++;
    }
    for (i = 0;i < 9;i++) {
        int countt = 0;
        for (j = 8;j >= 0;j--) {
            if (tmp[i][j] == 1) countt++;
            else {
                cnt1+=countt;
            }
        }
    }
    return cnt * height - cnt1 * hard;
}
void dfs(int bl,int n) {
    int i,j,k,loss;
    if (n == 0) {
        int cnt = 0;
        err = 0;
        for (j = 0;j <= 9;j++) {
            for (k = 0;k <= 12;k++) tmp[j][k] = mapp[j][k];
        }
        for (i = 1;i <= 4;i++) {
            cnt += drop(b[bl - 1 + i], step[i]);
            if (err == 1) return;
        }
        loss = calcLoss();
        if (dp[step[1]] < loss + cnt * removeS) dp[step[1]] = loss + cnt * removeS;
        if (dp[step[1]] == 140)
            i = i;
        return;
    }
    for (i = 0;i <= 8;i++) {
        step[5-n] = i;
        dfs(bl,n - 1);
    }
}
int main() {
    int n, i,j,k;
    FILE* in = fopen("input.txt", "r");
    FILE* out = fopen("output.txt", "w");
    block[0][0][0] = 1;
    block[1][0][0] = 1;
    block[1][0][1] = 1;
    block[2][0][0] = 1;
    block[2][1][0] = 1;
    block[3][0][0] = 1;
    block[3][0][1] = 1;
    block[3][0][2] = 1;
    block[4][0][0] = 1;
    block[4][1][0] = 1;
    block[4][2][0] = 1;
    block[5][0][0] = 1;
    block[5][0][1] = 1;
    block[5][1][0] = 1;
    block[6][0][0] = 1;
    block[6][1][0] = 1;
    block[6][1][1] = 1;
    block[7][0][0] = 1;
    block[7][0][1] = 1;
    block[7][1][1] = 1;
    block[8][0][1] = 1;
    block[8][1][0] = 1;
    block[8][1][1] = 1;
    fscanf(in,"%d", &n);
    for (i = 1;i <= n;i++) {
        fscanf(in,"%d", &b[i]);
        b[i]--;
    }
    for (i = 1;i <= n;i++) {
        for (j = 0;j < 9;j++) dp[j] = -100000000;
        dfs(i,4);
        int maxx = -100000000, maxi = -1;
        for (j = 0;j < 9;j++) {
            if (maxx < dp[j]) { maxx = dp[j]; maxi = j; }
        }
        if (maxx < -50000000) {
            printf("ERR!!!!!\n");
            printf("%d", i);
            return 0;
        }
        for (j = 0;j < 9;j++) {
            for (k = 0;k < 12;k++) tmp[j][k] = mapp[j][k];
        }
        drop(b[i], maxi);
        for (j = 0;j < 9;j++) {
            for (k = 0;k < 12;k++) mapp[j][k] = tmp[j][k];
        }
        ans[i] = maxi + 1;
        if (i % 100 == 0) printf("%d\n", i);
    }
    for (i = 1;i <= 50000;i++) {
        fprintf(out, "%d\n", ans[i]);
    }
    return 0;
}