파일 업로드

퍼즐 해결 2

profile
실행 시간 제한메모리 제한
1 초128 MB
📃 해결할 문제

민지는 특별한 퍼즐을 해결하려고 합니다. 퍼즐 보드 위에는 1x1 크기의 정사각형 여러 개가 붙어서 만들어진 세 개의 독립적인 물체가 있습니다. 각 물체는 하나 이상의 정사각형으로 이루어져 있고, 각 정사각형은 상하좌우로 서로 연결되어 있습니다. 민지의 목표는 이 세 물체를 상하좌우로 슬라이딩하여 서로 겹치지 않게 만드는 것입니다. 주어진 퍼즐 보드의 상태에서 세 물체를 분리하는 데 필요한 최소한의 개별 슬라이드 수를 결정해 주세요.

💻 입력
  • 줄 1: 단위 정사각형으로 구성된 각 물체 1, 2, 3의 수를 나타내는 세 개의 공백으로 구분된 정수: N1, N2, 그리고 N3.
  • 줄 2..1+N1: 각 줄은 물체 1의 일부분인 단일 정사각형의 남서쪽 모서리의 (x,y) 위치를 설명합니다. 모든 좌표는 0..9의 범위에 있습니다.
  • 줄 2+N1..1+N1+N2: 각 줄은 물체 2의 일부분인 단일 정사각형의 남서쪽 모서리의 (x,y) 위치를 설명합니다. 모든 좌표는 0..9의 범위에 있습니다.
  • 줄 2+N1+N2..1+N1+N2+N3: 각 줄은 물체 3의 일부분인 단일 정사각형의 남서쪽 모서리의 (x,y) 위치를 설명합니다. 모든 좌표는 0..9의 범위에 있습니다.
🖨️ 출력

세 물체를 분리하는 데 필요한 최소 이동 횟수, 또는 물체를 분리할 수 없는 경우 -1을 출력합니다.


💻 예제 입력 1
12 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 2
🖨️ 예제 출력 1
5

출처: USACO 2012 US Open, Silver Division Problem 1. Unlocking Blocks (Silver)