이차원 평면상에 변들이 좌표축에 평행한 L-모양 다각형의 장애물들이 있다. 이들 장애물들은 서로 겹치지 않고 또한 변이나 꼭지점에서 만나지 않는다.

로봇이 어느 한 지점에서 출발하여 정해진 도착지점으로 이들 장애물들을 피해서 이동하고자 한다. 이 로봇은 항상 좌표축과 평행하게 이동하며 장애물의 변을 따라서 이동할 수도 있다.

로봇이 출발지점에서 도착지점까지 이동하는 여러 경로들 중에서 꺾이는 횟수가 최소가 되는 경로를 찾고자 한다.

단, 로봇의 크기를 무시하여 로봇을 이차원 상의 점으로 표현할 수 있다고 가정한다. 또한, 로봇의 출발지점과 도착지점은 항상 장애물의 내부나 경계선에 놓여있지 않다.

아래 그림의 예를 통해서 로봇이 도착지점에 도달하기 위한 여러 경로가 있음을 알 수 있고, 또한 이 경우에서는 꺾이는 수가 3이 최소임을 알 수 있다.

L-모양 다각형의 장애물들, 출발지점, 도착지점이 입력으로 주어져 있을 때 로봇이 출발지점에서 도착지점으로 이동하는 경로 중 꺾이는 횟수가 최소인 것을 찾는 프로그램을 작성하시오.

실행시간은 1초를 초과할 수 없다. 부분점수는 없다.

로봇 timer 1s memory 128MB

로봇 1s 128MB