QUADTREE(四叉木反転)

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

入力として、与えられた文字列はXを基準として、上図に示す破片に変換することができる.結果Xの後ろの文字列要素は4つの領域に分かれているので、各領域が1つ完成し、最後にマージすればよい.各領域Treenは、「W」または「B」または新しいXが4つの領域に再分割された場合にのみ存在する.したがって、TREENが「W」または「B」である場合、TREENがXである場合、再帰的に4つの部分に分割され、小さな部分の問題に分割される.
入力時には,前から所定のN文字列を1つずつ読み出し,最後の要素まで1回だけ参照すればよいので,時間複雑度はO(N)である.(前回読み込んだ部分から再処理して、特定の重複は発生しません)
分割征服部分に属する問題であるが,分割征服の概念を利用して時間的複雑さを減らす戦略ではなく,自然に方法を見つける問題である.当初,四叉木圧縮自体が元素を分割圧縮した状態であったため,自然に問題を解決する方法は分割した元素のみを利用した.本当にこの問題を分割征服問題と見なすことができますか?

記憶に残る要素

文字列を読み取るとき、再帰関数では文字列の始点をint型整数として単独で送信する方法が使用されているのを見ました.ポインタ演算を使用する場合は、文字列自体を渡すだけです.ポインタを利用すると、コードも簡潔になり、工程ごとの起点が別々に計算されるので、工夫する必要はありません.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <time.h>
#include <string>

using namespace std;

string quadtree(char* picture, int start) {
	int next = 0;
	string tree0, tree1, tree2, tree3;

	if (picture[start] == 'x') {
		tree0 = 'x' + quadtree(picture, start + next + 1);
		next += tree0.length(); 
	}
	else {
		tree0 = picture[start + next];
		next++;
	}

	if (picture[start + next] == 'x') {
		tree1 = 'x' + quadtree(picture, start + next + 1);
		next += tree1.length();
	}
	else {
		tree1 = picture[start + next];
		next++;
	}

	if (picture[start + next] == 'x') {
		tree2 = 'x' + quadtree(picture, start + next + 1);
		next += tree2.length();
	}
	else {
		tree2 = picture[start + next];
		next++;
	}

	if (picture[start + next] == 'x') {
		tree3 = 'x' + quadtree(picture, start + next + 1);
		next += tree3.length();
	}
	else {
		tree3 = picture[start + next];
	}


	return tree2 + tree3 + tree0 + tree1;
}

int main() {
	clock_t start, end;
	double result;
	int testcase;
	scanf("%d", &testcase);
	getchar();

	for (int i = 0; i < testcase; i++) {
		char picture [1000];
		scanf("%[^\n]", picture);
		getchar();
		if (picture[0] != 'x') {
			printf("%s\n", picture);
			continue;
		}
		string ret = quadtree(picture, 1);
		ret = 'x' + ret;
		printf("%s\n", ret.c_str());


		//end = clock();
		//result = (double)(end - start);
		//printf("%f", result);
	}

	return 0;
}