[アルゴリズム]Algospot QUADREE

ソース:https://www.algospot.com/judge/problem/read/QUADTREE

質問する

四叉木(Quad Tree)は、大量の座標データを圧縮してメモリに格納する方法である.与えられた空間を常に4つに分割して再帰的に表すため、白黒画像を圧縮することで知られている四叉木と命名された.四叉木は2 N× 2 Nサイズの白黒画像を文字列に圧縮するには、次の手順に従います.
この図のすべての画素が黒である場合、図のサイズにかかわらず、この図の四叉木圧縮結果はbである.
この図のすべての画素が白色である場合、図の大きさにかかわらず、この図の四叉木圧縮結果はwである.
すべてのピクセルが同じ色でない場合は、画像の水平方向と垂直方向を2つの部分に分割し、各部分を4つのツリーに圧縮します.画像全体の圧縮結果はx(左上隅圧縮の結果)(右上隅圧縮の結果)(左下隅圧縮の結果)(右下隅圧縮の結果)である.例えば、図(a)の左上隅四分面はxwwwbに圧縮される.
図(a)及び図(b)は16×四叉木が16サイズの画像をどのように分割圧縮するかを示します.画像全体の圧縮結果はxxwww bxwxw bbw xxxwbbwwwwwbbbであった.
四叉木に圧縮された白黒画像を得る場合は、上下に反転した画像を四叉木に圧縮して出力するプログラムを作成します.

入力

1行目のテストケース数C(C≦50).すると、C行のそれぞれに四叉木に圧縮された画像があります.すべての文字列の長さは1000未満で、元の画像のサイズは220です.× 220を超えない.

しゅつりょく

各テストケースの1行の上下逆の画像を四叉木圧縮し、結果を出力します.

正しいコード

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;

int pos;
int i;

string reverse(string& pic)
{
    char pos = pic[i++];

    if(pos=='b')    return "b";
    if(pos=='w')    return "w";

    string topL=reverse(pic);
    string topR=reverse(pic);
    string botL=reverse(pic);
    string botR=reverse(pic);

    return "x" + botL + botR + topL + topR;
}

int main()
{
    int t;

    cin >> t;

    while(t--)
    {
        string pic;

        cin >> pic;

        cout << reverse(pic) << endl;

        i=0;
    }

    return 0;
}

解答と思考過程

どのように接近すればいいのか分からず、30分近く接近した.再帰関数では,2つのqueueを用いてそれぞれ上・下の思考を行うが,考え方は非常に複雑である.本には二つの方法が提案されている.
解凍と解凍

非解凍

解凍

解凍せずにqueueで解決しようと思ったのですが、思ったより複雑だったので本を参考にしました.
本の中の最初の方法は私の考えと似ていて、私が思っているより簡潔で具体的です.
また,第2の方法backtrackingを用いた解題コード自体は簡単である.しかし、事故自体は私の今のレベルでは難しいようです.
再帰的思考の力と表現力を養わなければならない.