2차원 평면상에 m개의 수직선과 n개의 수평선으로 이루어진 격자 형태의 도로망이 있다.

아래 그림은 7개의 수직선과 6개의 수평선으로 이루어진 도로망의 예이다.

수직선과 수평선이 만나는 교차점들 중 가장 왼쪽 아래 점의 위치는 (1,1)이고, 가장 오른쪽 위 점의 좌표는 (m,n)이다.

이 도로망을 운행하는 버스들이 k개 있고, 각 버스는 하나의 수평선 상의 두 교차점 사이 선분이나 하나의 수직선 상의 두 교차점 사이 선분을 왕복 운행한다.

각 버스는 운행하는 선분 사이의 모든 교차점(선분의 양 끝 교차점 포함)에서 정차한다.

출발지 교차점과 목적지 교차점 (출발지와 목적지는 다름)이 주어질 때, 출발지에서 목적지로 버스만을 이용하여 가려고 한다.

이용하는 버스의 최소 수를 구하는 프로그램을 작성하시오.

예를 들어, 8대의 버스가 다음과 같이 운행한다고 하자. 1번 버스: (2, 1) - (2, 2)

2번 버스: (1, 1) - (5, 1)

3번 버스: (3, 2) - (6, 2)

4번 버스: (5, 6) - (5, 1)

5번 버스: (1, 5) - (7, 5)

6번 버스: (7, 3) - (7, 6)

7번 버스: (2, 1) - (2, 6)

8번 버스: (3, 5) - (6, 5)

출발지가 (2, 1)이고 목적지가 (7, 4)라 하자.

한 가지 방법으로, 처음에 2번 버스를 타고 교차점 (5, 1)에서 내려, 4번 버스를 타고 (5, 5)에서 내리고, 5번 버스를 탄 후 (7, 5)에서 내려, 마지막으로 6번 버스를 타서 목적지 (7, 4)에서 내린다.

그러면 이용하는 버스 수는 4이다.

다른 방법으로, 7번 버스를 타고 (2, 5)에서 내려, 5번 버스를 타고 (7, 5)에서 내린 후, 마지막으로 6번 버스를 타서 목적지 (7, 4)에서 내린다.

그러면 이용하는 버스 수는 3이고 이것이 최소이다.

버스 갈아타기 timer 1s memory 256MB

버스 갈아타기 1s 256MB