XOR 6
시간 제한1초메모리 제한512 MB
N x N 이진 이미지가 주어질 때, 흰 화면에서 시작해 이 이미지를 만드는 최소 개수의 직사각형 XOR 연산을 찾는다.
문제
흑백 화면을 가진 휴대폰용 애플리케이션을 만들고 있다. 그림에서처럼 화면의 x좌표는 왼쪽에서, y좌표는 위쪽에서 시작한다. 이 애플리케이션에는 크기가 제각각인 여러 이미지가 필요하다. 이미지를 저장하는 대신 휴대폰 그래픽 라이브러리로 이미지를 만들려고 한다. 이미지를 그리기 시작할 때 화면의 모든 픽셀은 흰색이라고 가정한다. 휴대폰 라이브러리의 유일한 그래픽 연산은 XOR(L,R,T,B)이며, 왼쪽 위 좌표가 (L,T), 오른쪽 아래 좌표가 (R,B)인 직사각형의 픽셀 값을 뒤집는다. 여기서 L은 왼쪽, T는 위, R은 오른쪽, B는 아래 좌표를 뜻한다. 다른 그래픽 라이브러리에서는 인자의 순서가 다를 수 있다.
예로 Figure-3의 이미지를 보자. 모두 흰색인 이미지에 XOR(2,4,2,6)을 적용하면 Figure-1이 된다. Figure-1의 이미지에 XOR(3,6,4,7)을 적용하면 Figure-2가 되고, Figure-2의 이미지에 XOR(1,3,3,5)를 적용하면 마지막으로 Figure-3이 된다.
 |  |  |
| Figure-1 | Figure-2 | Figure-3 |
흑백 그림들이 주어졌을 때, 처음에 흰 화면인 상태에서 XOR 호출을 최대한 적게 사용해 각 그림을 만들어야 한다. 이미지를 설명하는 입력 파일들이 주어지며, 이러한 파일을 만드는 프로그램이 아니라 필요한 XOR 호출 인자를 담은 파일을 제출해야 한다.
입력
xor1.in부터 xor10.in까지의 텍스트 파일로 10개의 문제 인스턴스가 주어진다. 각 입력 파일의 구성은 다음과 같다. 입력 파일의 첫 줄에는 정수 N이 하나 있으며, 5 ≤ N ≤ 2000으로 이미지에 N개의 행과 N개의 열이 있음을 뜻한다. 나머지 줄은 이미지의 행을 위에서 아래로 나타낸다. 각 줄에는 N개의 정수가 있으며, 왼쪽에서 오른쪽으로 그 행의 픽셀 값을 나타낸다. 각 정수는 0 또는 1이고, 0은 흰 픽셀, 1은 검은 픽셀을 뜻한다.
출력
첫 줄에는 정수 K가 있다. K는 파일에 지정된 XOR 호출의 수이다. 다음 K개 줄은 이러한 호출을 첫 번째 호출부터 마지막으로 실행할 호출까지 나타낸다. 이 K개 줄은 각각 네 개의 정수, 즉 XOR 호출 인자 L, R, T, B를 그 순서대로 담는다.