왼손 법칙
시간 제한8초메모리 제한512 MB
단위 격자 벽으로 이루어진 미로에서 왼손 법칙을 따라 이동을 시뮬레이션하고, 출구까지의 걸음 수를 출력하거나 불가능하면 Impossible을 출력한다.
문제
왼손 법칙은 벽 따라가기라고도 불리며, 2차원 미로를 푸는 잘 알려진 전략이다. 이 전략은 다음과 같다. 미로에 들어간 뒤에는 왼손을 벽에 붙인 채로 출구에 도달할 때까지 걸어 다닌다. 실제로 이 전략이 어떤 종류의 미로를 해결한다는 것이 증명되어 있다.
여러분의 과제는 주어진 미로가 왼손 법칙으로 풀 수 있는지, 그리고 풀 수 있다면 출구에 도달하는 데 걸리는 걸음 수를 구하는 프로그램을 작성하는 것이다. 입구에서 출발하거나 인접한(북, 남, 동, 서) 칸으로 이동하는 것을 한 걸음으로 센다.
이 문제에서 미로는 2차원 격자 위에 놓인 벽들의 모임으로 표현된다. 일반적인 데카르트 좌표계를 사용하며, 양의 x축은 오른쪽, 양의 y축은 위쪽을 향한다. 각 벽은 x축 또는 y축에 평행한 선분으로 표현되고, 각 벽의 양 끝은 정수 좌표에 놓인다. 미로의 크기는 미로의 너비와 높이를 나타내는 W와 H로 주어진다. (0, 0), (W, 0), (W, H), (0, H)를 꼭짓점으로 하는 직사각형이 미로의 바깥 경계를 이룬다. 미로의 바깥은 미로의 입구를 제외하면 항상 벽으로 둘러싸여 있다. 입구는 양 끝이 (xE, yE)와 (xE', yE')인 선분으로 표현된다. 입구의 길이는 1이고 경계의 한 변 어딘가에 놓인다. 출구는 왼쪽 아래 꼭짓점이 (xX, yX)에 있는 단위 정사각형이다.
아래 그림에 미로의 몇 가지 예가 나와 있다. 이들은 예제 입력의 데이터셋에 대응한다.
그림 1: 미로의 예 (음영 처리된 정사각형이 출구를 나타낸다)
입력
입력은 여러 데이터셋으로 이루어진다.
각 데이터셋의 형식은 다음과 같다.
W H N
x1 y1 x1' y1'
x2 y2 x2' y2'
...
xN yN xN' yN'
xE yE xE' yE' xX yX
W와 H (0 < W, H ≤ 100)는 미로의 크기를 나타낸다. N은 미로 내부의 벽의 개수이다. 다음 N개의 줄은 벽의 위치를 주며, (xi, yi)와 (xi', yi')는 각 벽의 양 끝을 나타낸다 (1 ≤ i ≤ N). 마지막 줄은 입구와 출구의 위치를 준다. 입력으로 주어지는 모든 좌표는 정수 좌표이고 미로의 경계 안쪽에 있다고 가정할 수 있다. 또한 벽의 기술이 중복되지 않는다, 즉 어떤 벽의 끝점이 그 벽과 평행한 다른 벽과 공유되지 않는다고 가정할 수 있다.
입력은 세 개의 0이 있는 줄로 끝난다.
출력
각 데이터셋마다 출구에 도달하는 데 필요한 걸음 수를 한 줄에 출력한다. 주어진 미로를 풀 수 없다면 걸음 수 대신 “Impossible”을 출력한다.