포크 트리 @POJ1610 Quad Trees

이 문제를 통해 다음 네 갈래 나무를 연습했는데 사실은 매우 간단했다. 네 갈래 나무를 여러 갈래 나무로 삼아 구축하면 된다. 또 하나의 고전적인 응용은 바로 Trie(자전수)이다. 방법은 동태와 정태가 있고 두 갈래 나무와 네 갈래 나무 인덱스에 규칙이 있기 때문에 이를 통해 정태적인 방법을 채택하여 신속하게 인코딩할 수 있다.
이 문제는 N*N의 그림을 주고 이 그림에 네 갈래 나무를 만들어 인코딩용 나무를 구성하는 것이다.이 네 갈래 나무를 구축하는 복잡도는 O(M), M=N^2, M은 그림의 원소의 개수, 복잡도 단계와 네 갈래 나무 노드의 수는 선형 관계가 된다. 나머지는 본 문제에 대해 시뮬레이션이다. 코드는 다음과 같다.

#include <iostream>

#include <vector>

#include <string>

using namespace std;

const int MAXN = 600;

class CNODE

{

public:

    int X, Y, E;

    int flag, num;

public:

    CNODE() {}

    CNODE(int _x, int _y, int _e, int _f, int _n)

        : X(_x), Y(_y), E(_e), flag(_f), num(_n) {}

}node[MAXN * MAXN * 2];

int bin_map[MAXN][MAXN];

class CQUADTREE

{

public:

public:

    CQUADTREE() {}

    void Build(int r, int x, int y, int e)

    {

        if(e > 1)

        {

            Build(4 * r - 2, x, y, e / 2);

            Build(4 * r - 1, x, y + e / 2, e / 2);

            Build(4 * r, x + e / 2, y, e / 2);

            Build(4 * r + 1, x + e / 2, y + e / 2, e / 2);

            int i, judge = 0;

            for(i = 4 * r - 2; i < 4 * r + 2; i++)

            {

                if(node[i].flag)  break;

                judge |= (1 << node[i].num);

                if(judge == 3)  break;

            }

            if(i < 4 * r + 2)  node[r] = CNODE(x, y, e, 1, -1);

            else  node[r] = CNODE(x, y, e, 0, bin_map[x][y]);

        }

        else    //  

        {

            node[r] = CNODE(x, y, e, 0, bin_map[x][y]);

        }

    }

};

void go(int n)

{

    CQUADTREE tree;

    tree.Build(1, 0, 0, n);

    vector<int> Q;

    string ans = "";

    Q.push_back(1);

    for(int i = 0; i < Q.size(); i++)

    {

        if(node[Q[i]].flag)

        {

            ans += "1";

            for(int j = 4 * Q[i] - 2; j < 4 * Q[i] + 2; j++)

                Q.push_back(j);

        }

        else

        {

            ans += "0";

            if(node[Q[i]].num)  ans += "1";

            else  ans += "0";

        }

    }

    //cout << ans << endl;

    while(ans.length() % 4)  ans = "0" + ans;

    for(int i = 0; i < ans.length(); i += 4)

    {

        int tmp = 8 * (ans[i] - '0') +

            4 * (ans[i + 1] - '0') +

            2 * (ans[i + 2] - '0') +

            1 * (ans[i + 3] - '0');

        printf("%X", tmp);

    }

    printf("
");

}

int main()

{

    int T;

    scanf("%d", &T);

    while(T--)

    {

        int n;

        scanf("%d", &n);

        for(int i = 0; i < n; i++)

            for(int j = 0; j < n; j++)

                scanf("%d", &bin_map[i][j]);

        go(n);

    }

}