문제 개요

격자 동물(Lattice Animals) 문제는 주어진 크기의 격자 내에서 특정한 연결된 블록 조합의 수를 세는 문제입니다. 이 문제는 복잡한 알고리즘 없이도 완전 탐색을 통해 해결할 수 있으며, 사전에 가능한 모든 경우를 계산하여 표 형태로 저장한 후 질의에 따라 바로 답을 출력하는 방식으로 구현됩니다.

접근 방법

해당 문제는 가능한 모든 연결된 블록의 형태를 미리 생성하고, 각각의 블록이 주어진 너비와 높이 제약 안에 들어가는지를 확인하여 카운트하는 방식으로 해결됩니다. 회전 및 반전에 의해 동일한 형태가 되는 블록은 중복을 피하기 위해 정규화(normalization) 과정을 거칩니다.

구현 전략

다음은 주요 구현 단계입니다:

• 시작 위치에서 상하좌우로 확장하며 연결된 블록을 재귀적으로 생성합니다.
• 생성된 블록은 좌표를 최소값 기준으로 정렬하여 중복 여부를 판단합니다.
• 회전과 반전을 적용한 형태를 모두 고려하여 중복을 제거합니다.
• 모든 유효한 블록을 너비와 높이 제한에 맞춰 카운트합니다.

사전 계산 코드

#include <set>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long LL;
const int MAXN = 11;
const int INF = 0x3f3f3f3f;

struct Point {
    mutable int x, y;
    Point() {}
    Point(int xx, int yy) : x(xx), y(yy) {}
    bool operator<(const Point &other) const {
        if (x != other.x) return x < other.x;
        return y < other.y;
    }
    bool operator==(const Point &other) const {
        return x == other.x && y == other.y;
    }
};

typedef set<Point> Block;
set<Block> uniqueBlocks[MAXN], allBlocks[MAXN];
int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};

int result[MAXN][MAXN][MAXN]; // [size][width][height]

Block normalize(Block b) {
    int minX = INF, minY = INF;
    for (auto it = b.begin(); it != b.end(); ++it) {
        minX = min(minX, it->x);
        minY = min(minY, it->y);
    }
    for (auto it = b.begin(); it != b.end(); ++it) {
        const_cast<Point&>(*it).x -= minX;
        const_cast<Point&>(*it).y -= minY;
    }
    return b;
}

bool isVisited(int size, Block b) {
    auto it = uniqueBlocks[size].lower_bound(b);
    return it != uniqueBlocks[size].end() && *it == b;
}

Block rotate(Block b) {
    Block rotated;
    for (auto it = b.begin(); it != b.end(); ++it) {
        rotated.insert(Point(10 - it->y, it->x));
    }
    return normalize(rotated);
}

Block flipHorizontal(Block b) {
    Block flipped;
    for (auto it = b.begin(); it != b.end(); ++it) {
        flipped.insert(Point(it->x, 20 - it->y));
    }
    return normalize(flipped);
}

Block flipVertical(Block b) {
    Block flipped;
    for (auto it = b.begin(); it != b.end(); ++it) {
        flipped.insert(Point(20 - it->x, it->y));
    }
    return normalize(flipped);
}

void addBlock(int size, Block b) {
    allBlocks[size].insert(b);
    for (int i = 0; i < 4; ++i) {
        b = rotate(b);
        uniqueBlocks[size].insert(b);
        uniqueBlocks[size].insert(flipHorizontal(b));
        uniqueBlocks[size].insert(flipVertical(b));
    }
}

bool visited[MAXN][MAXN];
void generate(int size, Block current) {
    if (isVisited(size, current)) return;
    Block normalized = normalize(current);
    if (!isVisited(size, normalized)) addBlock(size, normalized);
    if (size == 10) return;

    Block candidates;
    for (auto it = current.begin(); it != current.end(); ++it) {
        for (int d = 0; d < 4; ++d) {
            int nx = it->x + dx[d], ny = it->y + dy[d];
            if (nx < 0 || ny < 0 || nx >= 10 || ny >= 10 || visited[nx][ny]) continue;
            candidates.insert(Point(nx, ny));
        }
    }

    for (auto it = candidates.begin(); it != candidates.end(); ++it) {
        current.insert(*it);
        visited[it->x][it->y] = true;
        generate(size + 1, current);
        visited[it->x][it->y] = false;
        current.erase(current.lower_bound(*it));
    }
}

void precompute() {
    Block initial;
    for (int i = 0; i < 5; ++i) {
        visited[0][i] = true;
        initial.insert(Point(0, i));
        generate(1, initial);
        visited[0][i] = false;
        initial.clear();
    }

    for (int sz = 1; sz <= 10; ++sz) {
        for (auto it = allBlocks[sz].begin(); it != allBlocks[sz].end(); ++it) {
            int maxX = 0, maxY = 0;
            for (auto pIt = it->begin(); pIt != it->end(); ++pIt) {
                maxX = max(maxX, pIt->x);
                maxY = max(maxY, pIt->y);
            }
            for (int w = 1; w <= 10; ++w) {
                for (int h = 1; h <= 10; ++h) {
                    if ((maxX < w && maxY < h) || (maxX < h && maxY < w)) {
                        ++result[sz][w][h];
                    }
                }
            }
        }
    }

    freopen("output.txt", "w", stdout);
    for (int i = 1; i <= 10; ++i) {
        for (int j = 1; j <= 10; ++j) {
            for (int k = 1; k <= 10; ++k) {
                printf("result[%d][%d][%d]=%d;\n", i, j, k, result[i][j][k]);
            }
        }
    }
}

int main() {
    precompute();
    return 0;
}

질의 처리 코드

사전 계산된 결과를 배열에 저장한 후, 입력에 따라 해당 값을 바로 출력합니다.

// 사전 계산된 결과 배열
int result[11][11][11] = {/* ... */};

int main() {
    int n, w, h;
    while (~scanf("%d %d %d", &n, &w, &h)) {
        printf("%d\n", result[n][w][h]);
    }
    return 0;
}