레이팅 미적용소들에 대해 잘 알려지지 않은 사실 하나는, 소들이 퍼즐을 사랑한다는 것이다! 베시(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을, 잠겨 있으면 0을 출력한다.
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 21Input details: Object 1 is made from 12 squares, object 2 is made from 3 squares, and object 3 is made from 5 squares.
riseoj 작성
출처 올림피아드 > USACO > 2011-2012 > US Open > Bronze