Quad Tree Compression
InterviewTime limit2sMemory limit128 MB
Given an N x N binary grid, recursively quadrant-compress it into a string using uniform-region shortcuts and parenthesized quadrant order.
- Level
Medium4 of 10
- Topics
- Divide and conquer, Recursion, Matrix
- Solved
- No attempts yet
Problem
You are given an N x N black-and-white image made only of 0 and 1. If every cell in a region has the same value, that region is represented by that one character. If a region contains both values, divide it into four equal parts and compress them in this order: upper left, upper right, lower left, lower right. Wrap the four compressed results in parentheses.
Print the compressed string for the entire image.
Input
The first line contains the image size N. N is a power of 2, and 1 <= N <= 64. The next N lines each contain a string of length N. Each character is either 0 or 1 and represents one cell of the image.
Output
Print the compressed string for the entire image.