레이팅 미적용소들에 대해 잘 알려지지 않은 사실 하나는, 소들이 퍼즐을 사랑한다는 것이다! 베시(Bessie)의 생일을 맞아, 농부 존(Farmer John)은 베시가 풀 만한 흥미로운 기계식 퍼즐을 선물했다. 이 퍼즐은 세 개의 단단한 물체로 이루어져 있으며, 각 물체는 1x1 단위 정사각형들을 붙여 만든 것이다. 각 물체는 "연결된" 모양이다. 즉, 물체 위의 한 정사각형에서 물체 위의 정사각형들을 통해 북, 남, 동, 서로 이동하여 물체 위의 다른 어떤 정사각형에도 도달할 수 있다.
물체는 북, 남, 동, 서 중 한 방향으로 한 단위씩 반복해서 밀어 움직일 수 있다. 퍼즐의 목표는 물체들을 움직여 서로 분리하는 것, 즉 물체들의 경계 상자가 더 이상 서로 양의 넓이만큼 겹치지 않게 만드는 것이다. 세 물체의 모양과 위치가 주어질 때, 물체들을 분리하는 데 필요한 개별 밀기 동작의 최소 횟수를 알아내는 것을 베시에게 도와주자. (이 문제의 그림은 생략되었다.)
첫째 줄: 공백으로 구분된 세 정수 N1, N2, N3. 각각 물체 1, 2, 3을 이루는 단위 정사각형의 수를 나타낸다.
둘째 줄부터 1+N1번째 줄까지: 물체 1의 각 정사각형의 남서쪽 꼭짓점의 (x,y) 위치 (좌표는 0..9 범위).
2+N1번째 줄부터 1+N1+N2번째 줄까지: 물체 2의 정사각형들 (좌표는 0..9 범위).
2+N1+N2번째 줄부터 1+N1+N2+N3번째 줄까지: 물체 3의 정사각형들 (좌표는 0..9 범위).
세 물체를 분리하는 데 필요한 최소 이동 횟수, 또는 물체들을 분리할 수 없으면 -1.
unlock.in · 출력을 쓸 파일 unlock.out12 3 5
0 0
1 0
2 0
3 0
3 1
0 1
0 2
0 3
0 4
1 4
2 4
3 4
2 1
2 2
1 2
2 3
3 3
4 3
4 4
4 25Output details: If we slide object 3 to the east by one position, then slide object 2 north by one position, then slide object 1 west by three positions, then the bounding boxes of the three objects will no longer share any overlap in common.
riseoj 작성
출처 올림피아드 > USACO > 2011-2012 > US Open > Silver