算法问题实战策略 QUADTREE
- 2019 年 10 月 26 日
- 笔记
地址 https://algospot.com/judge/problem/read/QUADTREE
将压缩字符串还原后翻转再次压缩的朴素做法 在数据量庞大的情况下是不可取的
所以需要在压缩的情况下进行翻转
图片可以分成四块 每块在颜色不统一的情况下又会分成四块 那么翻转也可以采取这种逐步将问题分解成小块翻转 然后再处理大块算法 最后的到结果的算法
代码如下
#include <iostream> #include <string> using namespace std; /* 4 w xbwwb xbwxwbbwb xxwwwbxwxwbbbwwxxxwwbbbwwwwbb ======================================= w xwbbw xxbwwbbbw xxwbxwwxbbwwbwbxwbwwxwwwxbbwb */ int n; string reverse(string::iterator& it) { char head = *it; ++it; if (head == 'b' || head == 'w') return string(1, head); string upperLeft = reverse(it); string upperRight = reverse(it); string lowerLeft = reverse(it); string lowerRight = reverse(it); return string(1,'x') + lowerLeft + lowerRight + upperLeft + upperRight; } int main() { cin >> n; while (n--) { string s; cin >> s; string::iterator it = s.begin(); cout << reverse(it) << endl; } return 0; }
