주차장

ACM ICPC 아시아 지역예선 대회가 열렸던 백범기념관에는 가로 세로가 각각 6칸인 주차장이 있다. 주차장의 행은 위에서 아래로 1부터 6까지 차례로 번호가 매겨져 있고, 열도 마찬가지 방식으로 왼쪽에서 오른쪽으로 번호가 매겨져 있다. 주차장에 출입구는 셋째 행의 오른쪽에 오직 한 곳에만 있다.

	1	2	3	4	5	6
1	2					5
2	6			7
3		1					⇒출구
4
5	3				4
6			8

주차장에는 대의 자동차가 주차되어 있다. 그것들 중에 당신의 자동차가 있는데, 불행하게도 다른 차들이 당신 차를 가로막고 있어서 주차장에서 쉽게 빠져 나갈 수가 없다.  그렇지만 자동차의 기어는 모두 중립에 놓여 있어서, 당신과 당신 친구는 자동차를 앞뒤로 옮길 수 있다. 다른 자동차는 물론 당신 자동차도 운전하거나 회전할 수는 없다.

문제는 크기가 칸인 당신 자동차를 주차장 바깥으로 옮기는데 필요한 최소 단계를 구하는 것이다. 한 단계라는 것은 자동차 한대를 한 칸 옮기는 것을 말한다. 어떤 다른 자동차도 주차장 바깥으로 옮길 수 없다. 자동차는 오직 두 종류만이 존재한다. 한 종류는 그 크기가 칸이고 다른 종류의 크기는 칸이다. 자동차는 두 축 중에서 긴축 방향으로만 옮길 수 있다.

주어진 예에서 이고 당신 자동차의 번호는 1이다. 아래에 당신 자동차를 주차장 밖으로 옮기는데 최소로 필요한 18단계가 주어져 있다: 4←←←, 2→, 6↑, 3↑, 8←←, 5↓↓↓, 7↓↓, 1→→→→→.

프로그램 이름은 park.cpp, 실행 파일의 이름은 park.exe, 프로그램 설명 파일 이름은 park.hwp로 하고, 프로그램의 실행시간은 3초를 초과할 수 없다. 부분 점수는 없다.

입력 형식

입력 파일의 이름은 INPUT.TXT로 한다. 첫째 줄에 자동차의 수 이 주어진다. 다음 개의 줄에는 번호가 인 자동차에 대한 기술이 주어진다. 각 줄은 네 정수를 가지는데, 그것들은 길이 , 방향 , 그리고 출발(왼쪽 위) 좌표 (열 번호) 그리고 (행 번호)이다. 인접한 정수들 사이에는 공백이 하나 있다. 은 자동차가 수평으로 주차되어 있음을 나타낸다. 그렇지 않으면 수직으로 주차되어 있다. 다음 제한 조건이 성립한다: , , . 당신의 자동차는 자동차의 수 이 주어진 바로 다음 줄에 (즉, 입력 파일의 둘째 줄에) 주어져 있다. 당신 자동차는 반드시 출입구를 통해서 주차장 바깥으로 옮겨야 한다.

2004 가을학기 문제해결기법	문제 #12

출력 형식

출력 파일의 이름은 OUTPUT.TXT로 한다. 한 줄에 당신 자동차를 주차장 바깥으로 옮기는데 필요한 최소 단계의 수를 나타내는 정수를 출력한다. 만약 주차장 밖으로 옮길 수 없으면  -1을 출력한다.

입력과 출력의 예

입력(input.txt)

8

2 1 2 3

2 1 1 1

2 0 1 5

2 1 5 5

3 0 6 1

3 0 1 2

3 0 4 2

3 1 3 6

출력(output.txt)

18