algospot.com :: 과거 게시판: [editorial] E. Mini Blokus

[editorial] E. Mini Blokus

E - Mini Blokus
Preview
이번 대회에서 유일하게 풀리지 않은 문제였습니다. 만점방지용 문제로 출제되었다는 말이 있지만, 사실여부는 확인해 드릴 수 없습니다[?]

문제를 읽자마자 "모든 경우를 다 구해야겠다"는 느낌을 주는 문제이고, "코딩이 귀찮을 것 같은데?"라는 의문을 떨쳐버릴 수 없으셨을 겁니다. 실제로 솔루션을 만드는 Setter 입장에서도 처음 생각과는 다르게 쉽게 풀리지 않아서 고생이 많았습니다 ㅠㅠ 난이도 조절 잘할게요... 흑흑

Problem Description
4개 이하로 만들 수 있는 9가지 모양의 테트로미노 블럭을 사용하여, 현재 보드에 최대한 많이 채웠을 때 몇 칸이나 채울 수 있는가? 단 블럭은 보드의 Left-Top Cell을 지나야 하고, 각 블럭들은 꼭지점으로만 연결되어 있어야 한다. (자세한 설명은 실제 문제를 참고해 주세요.)
Analysis
블럭이 9가지[?] 밖에 없으므로, 모든 경우를 Try 하는 방법 밖에 없습니다. 우선 어떤 블럭이 있으면, 크게 세 가지 부분으로 나눌 수 있습니다. 아래의 그림을 살펴봅시다.

위는 4칸짜리 ㄴ자모양의 블럭을 나타내며, 간단하게 세 가지 색으로 구분해 보았습니다. 각각의 색깔은 다음을 의미합니다.

파란색 : 실제로 블럭이 놓여지는 위치입니다. 해당 칸에는 장애물이나 다른 블럭이 존재하면 놓을 수 없습니다.
회색 : 해당 좌표에는 다른 블럭이 존재할 수 없습니다. 현재 놓을 블럭과 변을 공유하기 때문입니다.
빨간색 : 파란색의 블럭을 놓게 된 경우, 다른 블럭들이 지나갈 수 있는 위치입니다.

각 블럭이 회전연산도 되고, 대칭연산도 되기 때문에, 9가지의 블럭 데이터를 만들어두고 회전/대칭 연산을 해 가면서 테스트하는 방법도 있겠지만, 각 연산에 들어가는 시간을 나름 최적화하기 위해서 놓일 수 있는 블럭 데이터를 직접 생성하는 쪽으로 구현하였습니다. (initBlock 함수)

그 다음부터는 실제로 Back Tracking을 통해서 모든 경우를 테스트하게 되었습니다. 거의 유일하게 넣은 컷이라고 하면

위와 같이 제일 왼쪽 위에 z자 모양의 블럭을 두었다고 가정합시다. 이제 다음 블럭은 1, 2, 3에 놓을 수 있게 됩니다. 1)에 아직 사용하지 않은 8개의 블럭을 모두 Try 해 볼 수 있겠지요. 1에 블럭을 두는 모든 경우를 고려했다면, 이제 1이 있던 위치에 "장애물"을 설치합니다. (장애물을 설치하는 이유는, 어차피 1에 블럭이 놓여져 있는 경우의 최적해는 이미 알고 있기 때문에 중복해서 계산할 필요가 없기 때문입니다.)

네. 말로 설명하는 것은 여기까지가 전부입니다. 나머지는 implementation의 문제로 넘어가겠네요 :D

Source Code

#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int dx[4] = {-1, 0, 0, 1};
int dy[4] = {0, -1, 1, 0};
int tx[4] = {-1, -1, 1, 1};
int ty[4] = {-1, 1, -1, 1};
long long state;
struct Block
{
    vector < pair<int, int > > pos;
    int sum;
    int shape;
    Block() : sum(-1), shape(-1) {}
    bool operator < (const Block &a) const
    {
        if (a.pos.size() != pos.size()) return pos.size() < a.pos.size();
        for (int i = 0; i < pos.size(); ++i)
            if ( pos[i] != a.pos[i] ) return pos[i] < a.pos[i];
        return false;
    }
    bool operator == (const Block &a) const
    {
        if (a.pos.size() != pos.size()) return false;
        for (int i = 0; i < pos.size(); ++i)
            if (pos[i] != a.pos[i]) return false;
        return true;
    }
    int getSum()
    {
        if (sum != -1) return sum;
        sum = 0;
        for (int i = 0; i < pos.size(); ++i)
            for (int j = i + 1; j < pos.size(); ++j)
            {
                sum += (pos[i].first - pos[j].first) * (pos[i].first - pos[j].first);
                sum += (pos[i].second - pos[j].second) * (pos[i].second - pos[j].second);
            }
        return sum;
    }
};
int n, m;
vector<string> board;
int ret;
vector< Block > block;
vector< Block > adj;
int table[32][32];
void initBlock()
{
    Block one;
    one.pos.push_back( make_pair( 0, 0 ));
    block.push_back( one );
    int prev = 0, next = 1;
    for (int size = 1; size <= 3; ++size)
    {
        for (int i = prev; i < next; ++i)
        {
            for (int j = 0; j < size; ++j)
            {
                for (int k = 0; k < 4; ++k)
                {
                    Block nx_state = block[i];
                    nx_state.pos.push_back( block[i].pos[j] );
                    nx_state.pos[ size ].first += dx[k];
                    nx_state.pos[ size ].second += dy[k];
                    bool dup = false;
                    for (int l = 0; l < size; ++l)
                        if ( nx_state.pos[size] == nx_state.pos[l] ) dup = true;
                    if (!dup)
                    {
                        sort( nx_state.pos.begin(), nx_state.pos.end() );
                        block.push_back( nx_state );
                    }
                }
            }
        }
        sort( block.begin(), block.end() );
        block.erase( unique( block.begin(), block.end() ), block.end() );
        prev = next;
        next = block.size();
    }
    adj.resize( block.size() );
    adj[0].pos.push_back( make_pair( 0, 0 ) );
    for (int i = 0; i < block.size(); ++i)
    {
        for (int j = 0; j < block[i].pos.size(); ++j)
        {
            for (int k = 0; k < 4; ++k)
                adj[i].pos.push_back( make_pair( block[i].pos[j].first + dx[k],
                            block[i].pos[j].second + dy[k] ) );
        }
        sort( adj[i].pos.begin(), adj[i].pos.end() );
        adj[i].pos.erase( unique( adj[i].pos.begin(), adj[i].pos.end() ),
                adj[i].pos.end() );
    }
    for (int i = 0; i < block.size(); ++i)
    {
        int bsz = block[i].pos.size(), bsum = block[i].getSum();
        if ( bsz == 1 && bsum ==  0 ) block[i].shape = 0;
        if ( bsz == 2 && bsum ==  1 ) block[i].shape = 1;
        if ( bsz == 3 && bsum ==  4 ) block[i].shape = 2;
        if ( bsz == 3 && bsum ==  6 ) block[i].shape = 3;
        if ( bsz == 4 && bsum == 20 ) block[i].shape = 4;
        if ( bsz == 4 && bsum == 14 ) block[i].shape = 5;
        if ( bsz == 4 && bsum == 12 ) block[i].shape = 6;
        if ( bsz == 4 && bsum == 11 ) block[i].shape = 7;
        if ( bsz == 4 && bsum ==  8 ) block[i].shape = 8;
    }
    for (int i = 0; i < block.size(); ++i)
        for (int j = i + 1; j < block.size(); ++j)
        {
            if (block[i].shape > block[j].shape)
            {
                swap(block[i], block[j]);
                swap(adj[i], adj[j]);
            }
        }
}
void go( vector< pair< int, int> > remain, int score, int index )
{
    if (ret < score) ret = score;
    if (ret == 50) return;
    int cx, cy;
    for (int start = 0; start < remain.size(); ++start)
    {
        cx = remain[start].first;
        cy = remain[start].second;
        for (int i = 0; i < block.size(); ++i)
        {
            if (( index & (1 << block[i].shape) ) == 0) continue;
            bool impos = false;
            for (int j = 0; j < block[i].pos.size(); ++j)
            {
                int x = cx + block[i].pos[j].first;
                int y = cy + block[i].pos[j].second;
                if (x < 0 || y < 0 || x == n || y == m) { impos = true; break; }
                if (table[x][y] < 0) { impos = true; break; }
            }
            if (!impos)
            {
                for (int j = 0; j < adj[i].pos.size(); ++j)
                {
                    int x = cx + adj[i].pos[j].first;
                    int y = cy + adj[i].pos[j].second;
                    if (x < 0 || y < 0 || x == n || y == m) continue;
                    table[x][y]--;
                }
                vector< pair< int, int> > nr = vector< pair< int, int> > (
                        remain.begin() + start, remain.end() );
                for (int j = 0; j < block[i].pos.size(); ++j)
                {
                    for (int k = 0; k < 4; ++k)
                    {
                        int x = cx + block[i].pos[j].first + tx[k];
                        int y = cy + block[i].pos[j].second + ty[k];
                        if (x < 0 || y < 0 || x == n || y == m) continue;
                        if (table[x][y] == 0)
                        {
                            nr.push_back( make_pair( x, y ) );
                        }
                    }
                }
                int nsc = score + block[i].pos.size();
                if (nsc == 0) nsc = 50;
                go( nr, nsc, index - (1 << block[i].shape));
                for (int j = 0; j < adj[i].pos.size(); ++j)
                {
                    int x = cx + adj[i].pos[j].first;
                    int y = cy + adj[i].pos[j].second;
                    if (x < 0 || y < 0 || x == n || y == m) continue;
                    table[x][y]++;
                }
            }
        }
        table[cx][cy]--;
    }
    for (int start = 0; start < remain.size(); ++start)
        table[remain[start].first][remain[start].second]++;
}
int main()
{
    initBlock();
    int T;
    char tmp[1000];
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d", &n, &m);
        board.resize(n);
        for (int i = 0; i < n; ++i)
        {
            scanf("%s", tmp);
            board[i] = tmp;
        }
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                if (board[i][j] == '.') table[i][j] = 0; else table[i][j] = -1;
        ret = -29;
        vector < pair<int, int> > remain;
        if (table[0][0] == 0) remain.push_back( make_pair( 0, 0 ));
        state = 0;
        go( remain, -29, (1 << 9) - 1 );
        cout << ret << endl;
    }
}

[이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

14년 전

0개의 댓글이 있습니다.

정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.

SINCE 2007

다가오는 이벤트들

[editorial] E. Mini Blokus

0개의 댓글이 있습니다.