쿼드트리

• 그냥 시키는대로 구현하면 되는 문제.
• 쿼드트리로 압축한 데이터의 크기만을 구하는 문제였던 색종이 만들기에서는 반복으로 구현했지만, 여기에서는 재귀를 써서 구현했다.
• 시간복잡도는 N*N + (N/2 * N/2) + (N/4 * N/4) + … + (1 * 1) = (N^2)/3 = O(N^2)

"""Solution code for "BOJ 1992. 쿼드트리".

- Problem link: https://www.acmicpc.net/problem/1992
- Solution link: http://www.teferi.net/ps/problems/boj/1992
"""


def solve(data, r, c, size):
    if size == 1:
        return data[r][c]
    else:
        size //= 2
        quad = ''.join([solve(data, r, c, size),
                        solve(data, r, c + size, size),
                        solve(data, r + size, c, size),
                        solve(data, r + size, c + size, size)])
        if quad == '1111':
            return '1'
        elif quad == '0000':
            return '0'
        else:
            return f'({quad})'


def main():
    N = int(input())
    data = [input() for _ in range(N)]

    print(solve(data, 0, 0, N))


if __name__ == '__main__':
    main()