시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 2757 | 580 | 426 | 20.510% |
전기 회로에서 두 점을 전선으로 이을 때, 길이는 짧을 수록 좋다.
크기가 N×M인 비어있는 회로판에서 두 점 A1과 A2, 그리고 B1와 B2를 전선을 이용해서 이으려고 한다. 전선은 항상 그리드의 수직, 수평선 위에 있어야 한다. 또, 두 직선은 접하면 안 된다. 이 경우에 필요한 전선의 길이의 최솟값을 구하는 프로그램을 작성하시오. 전선은 회로판 바깥으로 나갈 수 없다.
첫째 줄에 회로판의 크기 N과 M이 주어진다. (2 ≤ N, M ≤ 100)
다음 네 줄에는 A1, A2, B1, B2의 좌표가 주어진다. 점의 좌표는 두 정수의 쌍으로 이루어져 있고, 첫 번째 좌표는 0 이상 N 이하이며 두 번째 좌표는 0 이상 M 이하이다. 어떤 점도 같은 위치에 있지 않다.
A1과 A2, 그리고 B1과 B2를 연결하는데 필요한 전선의 길이의 최솟값을 출력한다. 만약, 불가능한 경우에는 "IMPOSSIBLE"을 출력한다.
6 6 2 1 5 4 4 0 4 5
15
6 3 2 3 4 0 0 2 6 1
IMPOSSIBLE