[アルゴリズム]ドミノ骨牌(三星)

https://www.acmicpc.net/problem/19235

個人的には、この問題はこれまでに解いたすべての三星問題の中で最も難しい問題だと思います.
この問題は各種の技能と困難なアルゴリズムを要求しない.すなわち,時間的複雑さや空間的複雑さを考慮せずに,完全探索に集中するだけである.しかし,機能実装においては,最も重要な各ステップが誤りやすいので,よく考えなければならない.

[手順]

棒を下ろします.

、削除する棒線がある場合は削除します.

で取り除かれた棒状線は、落下が必要な棒状物がある場合に落下する.△この時、棒が1本も離れられない.

(2~3)の動作を、クリア可能なレバーがなくなるまで続けます.

ロッドの浅部5.棒の浅い部分に棒がある場合は、それを下に置いて、それがなくなるまで置きます.

[再構築と効率]

1.処理基板実装

青板と緑板のシミュレーション過程を別々に実現すると,コードはかなり乱雑になる.実際には、2つのマザーボードでサポートされている機能は同じなので、1つの関数内で処理することが望ましい.1つの関数では、青い板の場合、緑の板を分ける場合に行うことができますが、これもかなりのミスを招きます.プログラマーはエラー要因の多いコードを書くべきではありません.(これは犯罪です)つまり、スケートボードはそのままで、落ちた棒を回すだけでいいということです.グリーンボードの時はそのまま落ちて、グリーンボードの時(x,y)->(y,x)は回転に変換!

2.関数で割る。(AOP)

すべての機能を関数に分割すると、メンテナンスの観点からは良いが、所定時間内に実現しなければならない観点から、関数の数が増加し、機能が混同される可能性がある.実際、どの機能を関数に減らして使用し、再構築するかは、科学分野ではなく芸術分野に近いと思います.一般的に,筆者は誤りや常用,役割を明確に区別する部分を関数に分けている.共有関数については,以下のように考える.
1.範囲確認関数
現在のバーが範囲内にあるかどうかを確認します.このシミュレーションでは、範囲の確認が頻繁に行われます.
2.回転関数
役割が明確である.グリーンプレートに使用したものをブループレートに使うために棒を回します.関数を作成する必要はありませんが、コードがすべて実装された後、コードを再チェックするときはかなり直感的です.
3.ロッド落下関数
この問題では棒がずっと下に落ちている.この部分は実装部分全体にわたって大きな部分を占め,これらの大きな論理ブロックを分離してエラーを防止する.
4.ブロックのマージ
棒を落とした時にくっついた棒も一緒に落とすため、二重機能を体現しています.
機能も適切なコードブロックサイズがあり、役割が明確です.

[実装]

#include <bits/stdc++.h>
using namespace std;
#define Board vector<vector<int>>
struct Block
{
    int y, x;
};
int score = 0, number_blocks = 0;
Board green_board(6, vector<int>(4));
Board blue_board(6, vector<int>(4));
vector<vector<Block>> Blocks({{{0, 0}}, {{0, 0}}, {{0, 0}, {0, 1}}, {{0, 0}, {1, 0}}});
int N;
void rotate(vector<Block> &blocks) 
{
    for (auto &block : blocks)
        swap(block.y, block.x);
}
bool isRange(Board &board, vector<Block> blocks)
{
    for (auto &block : blocks)
    {
        if (block.y <= 5 && block.y >= 0 && block.x >= 0 && block.x <= 3 && board[block.y][block.x] == 0)
            continue;
        return false;
    }
    return true;
}
void down(int number, Board &board, vector<Block> blocks)
{
    for (auto &block : blocks)
        board[block.y][block.x] = 0;
    while (1)
    {
        vector<Block> next = blocks;
        for (auto &block : next)
            block.y += 1;
        if (isRange(board, next))
            swap(next, blocks);
        else
            break;
    }
    for (auto &block : blocks)
        board[block.y][block.x] = number;
}
vector<Block> comb_block(Board &board, int y, int x)
{
    vector<Block> blocks({{y, x}});
    int number = board[y][x];
    if (y >= 1 && board[y - 1][x] == number)
        blocks.push_back({y - 1, x});
    else if (y <= 1 && board[y + 1][x] == number)
        blocks.push_back({y + 1, x});
    else if (x <= 2 && board[y][x + 1] == number)
        blocks.push_back({y, x + 1});
    else if (x >= 1 && board[y][x - 1] == number)
        blocks.push_back({y, x - 1});
    return blocks;
}
void go(int number, Board &board, vector<Block> blocks)
{
    //  
    int rotate_y = 100; //평행이동지점
    for (auto &block : blocks)
        rotate_y = min(rotate_y, block.y);
    for (auto &block : blocks)
    {
        block.y -= rotate_y; //평행이동 및 board에 채워넣기
    }

    //2.막히는 지점이 나올때까지 떨어트리기
    down(number, board, blocks);
    int before = -1;
    //3.지울 수 있는걸 한번에 다 지우기 밑에서 부터 체크
    while (before != score)
    {
        before = score;
        for (int y = 0; y <=5; y++)
        {
            int line_length = 0;
            for (int x = 0; x <= 3; x++)
            {
                if (board[y][x] != 0)
                    line_length++;
            }
            if (line_length == 4) //full
            {
                for (int x = 0; x <= 3; x++)
                    board[y][x] = 0;
                score++;
            }
        }
        //4.이때 같은 블록은 같이 떨어져야함 //어떻게 체크하지
        for (int y = 5; y >= 0; y--)
            for (int x = 0; x <= 3; x++)
                if (board[y][x] != 0)
                    down(board[y][x], board, comb_block(board, y, x)); //같은블록은 합쳐서 한번에 내리기;
    }
    //5. 3->4의 작업을 지울 수 있는게 없을때까지 반복
    //6 옅은부분 체크
    int howManyDown = 0;
    for (int y = 0; y <= 1 && howManyDown == 0; y++)
    {
        for (int x = 0; x <= 3; x++)
        {
            if (board[y][x] != 0)
            {
                howManyDown = 2 - y;
                break;
            }
        }
    }
    if (howManyDown > 0)
    {
        //7 옅은부분 만큼 밑으로 내리기
        for (int y = 5; y >= howManyDown; y--)
        {
            for (int x = 0; x <= 3; x++)
            {
                board[y][x] = board[y - howManyDown][x];
            }
        }
        //옅은부분 지우기
        for (int y = howManyDown-1; y >= 0; y--)
        {
            for (int x = 0; x <= 3; x++)
                board[y][x] = 0;
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> N;
    int num = 0;
    while (N-- > 0)
    {
        num++;
        int t, x, y;
        cin >> t >> y >> x;
        vector<Block> next = Blocks[t];
        for (auto &block : next)
        {
            block.y += y;
            block.x += x;
        }
        go(num, green_board, next); // 그린보드 작업
        rotate(next); ///블루보드에 넣기 위해 회전
        go(num, blue_board, next); //블루보드 작업
    }
    for (int y = 2; y <= 5; y++)
        for (int x = 0; x <= 3; x++)
        {
            if (green_board[y][x] != 0)
                number_blocks++;
            if (blue_board[y][x] != 0)
                number_blocks++;
        }
    cout << score << "\n" << number_blocks;
    return 0;
}