연결

시간 제한1초메모리 제한128 MB

요약
N x M 격자 위에서 A1과 A2를 잇는 선과 B1과 B2를 잇는 선을 서로 만나지 않게 놓을 때, 두 선 길이의 합의 최솟값을 구한다.
난이도

어려움10점 중 8점

유형
그래프, 최단 경로, BFS, 구현
정답자
아직 제출이 없습니다

문제

전기 회로에서 두 점을 전선으로 이을 때, 전선은 짧을수록 좋다.

크기가 N×MN \times M인 비어 있는 회로판 위에 네 점 A1A_1, A2A_2, B1B_1, B2B_2가 주어진다. A1A_1과 A2A_2를 하나의 전선으로 잇고, B1B_1과 B2B_2를 또 다른 전선으로 이으려고 한다.

회로판은 격자이며, 각 격자점의 좌표는 (x,y)(x, y) (0≤x≤N0 \le x \le N, 0≤y≤M0 \le y \le M)로 나타낸다. 전선은 항상 격자의 수직 또는 수평 방향 단위 선분을 따라서만 놓을 수 있고, 회로판 바깥으로 나갈 수 없다.

두 전선은 서로 닿으면 안 된다. 즉, 두 전선은 어떤 격자점도 공유할 수 없고 서로 교차할 수도 없다. (두 전선이 한 칸 간격을 두고 나란히 지나가는 것은 괜찮다.)

두 전선의 길이의 합의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 회로판의 크기 NN과 MM이 공백으로 구분되어 주어진다. (2≤N,M≤1002 \le N, M \le 100)

이어지는 네 줄에 각각 A1A_1, A2A_2, B1B_1, B2B_2의 좌표가 순서대로 주어진다. 각 좌표는 두 정수 xx와 yy로 이루어지며, 0≤x≤N0 \le x \le N, 0≤y≤M0 \le y \le M을 만족한다. 네 점의 위치는 모두 서로 다르다.

출력

A1A_1과 A2A_2, 그리고 B1B_1과 B2B_2를 잇는 데 필요한 두 전선의 길이의 합의 최솟값을 출력한다. 조건에 맞게 두 전선을 놓는 것이 불가능하면 IMPOSSIBLE을 출력한다.

예제3

  1. 예제 1

    입력
    6 6
    2 1
    5 4
    4 0
    4 5
    
    예상 출력
    15
    
  2. 예제 2

    입력
    6 3
    2 3
    4 0
    0 2
    6 1
    
    예상 출력
    IMPOSSIBLE
    
  3. 예제 3

    입력
    3 2
    0 0
    3 0
    0 1
    3 1
    
    예상 출력
    6