XOR 5
시간 제한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은 검은색 픽셀을 나타낸다.
출력
첫 줄에는 파일에 지정한 XOR 호출 횟수 K가 들어간다. 다음 K개 줄은 첫 호출부터 마지막으로 실행할 호출까지를 나타낸다. 이 K개 줄 각각에는 XOR 호출 인자 L, R, T, B가 이 순서대로 들어간다.