이상한 화가
시간 제한1초메모리 제한128 MB
재귀적으로 사분면을 흑백으로 칠하는 규칙으로 만들 수 있는 그림 중 주어진 N x N 그림과 차이가 가장 적은 그림과 그 차이값을 구하는 문제입니다.
문제
Josip은 흰색과 검은색으로 이루어진 정사각형 그림을 특이한 재귀 과정으로 그린다. 그림의 크기는 N x N 픽셀이며, N은 2의 거듭제곱이다. 각 픽셀은 흰색(0) 또는 검은색(1)이다.
정사각형이 한 픽셀뿐이면, 그 픽셀을 원하는 색으로 칠한다. 그보다 큰 정사각형은 네 개의 같은 크기 정사각형으로 나눈 뒤, 그중 하나를 전부 흰색으로 칠하고, 다른 하나를 전부 검은색으로 칠한다. 남은 두 정사각형에는 같은 과정을 재귀적으로 적용한다.
원하는 그림 중에는 이 과정으로 정확히 만들 수 없는 것도 있다. 원하는 그림이 주어졌을 때, 만들 수 있는 그림 중 차이가 가장 작은 그림을 찾아라. 두 그림의 차이는 같은 위치의 픽셀 색이 서로 다른 개수이다.
입력
첫째 줄에 원하는 그림의 크기 N (1 <= N <= 512)이 주어진다. N은 2의 거듭제곱이다.
다음 N개 줄에는 길이 N인 0과 1로 이루어진 문자열이 주어지며, 원하는 그림을 나타낸다.
출력
첫째 줄에 만들 수 있는 최소 차이를 출력한다.
다음 N개 줄에는 그 최소 차이를 달성하는 만들 수 있는 그림을 입력과 같은 형식으로 출력한다.
최적의 그림이 여러 개라면 그중 아무거나 출력해도 된다.