격자 숲

정수 격자에서 한 번에 한 칸씩 움직이며, 멈추는 모든 나무에서 원점이 보이도록 유지하면서 (x, y)에서 원점까지 가는 최단 시간을 구한다.

보통5수학정수론BFS그래프아직 제출이 없습니다시간 제한1초메모리 제한32 MB

문제

용훈이는 격자 숲에서 길을 잃었다. 이 숲에는 좌표평면의 정수 좌표마다 나무가 한 그루씩 서 있고, 원점 (0,0)(0, 0)에는 나무 대신 용훈이의 집이 있다. 다행히 멀리 보이는 집 덕분에 용훈이는 자기 위치를 알아냈다. 용훈이는 집에서 동쪽으로 xx, 북쪽으로 yy만큼 떨어진 나무 (x,y)(x, y) 아래에 서 있다.

용훈이는 동, 서, 남, 북 중 한 방향을 골라 이동하고, 한 번 이동하기 시작하면 다음 나무나 집에 닿을 때까지 멈추지 않는다. 나무 (a,b)(a, b)에서 한 번 이동하면 (a+1,b)(a+1, b), (a1,b)(a-1, b), (a,b+1)(a, b+1), (a,b1)(a, b-1) 중 하나에 도착하고 시간이 11만큼 흐른다. 좌표가 음수인 자리로도 갈 수 있다.

방향 감각을 유지하려면 용훈이가 거치는 모든 나무에서 집이 보여야 한다. 나무와 집은 매우 작아서 점으로 본다. 나무 (a,b)(a, b)에서 집이 보인다는 것은 두 점 (a,b)(a, b)(0,0)(0, 0)을 잇는 선분 위에 양 끝을 뺀 다른 나무가 하나도 없다는 뜻이다.

용훈이의 처음 좌표가 주어지면 집에 도착하는 데 걸리는 가장 짧은 시간을 구하는 프로그램을 작성하여라.

입력

첫째 줄에 용훈이의 xx좌표와 yy좌표가 공백을 사이에 두고 주어진다. (0x,y1080 \le x, y \le 108)

용훈이의 처음 위치에서 집이 보이는 것은 보장된다. (x,y)=(0,0)(x, y) = (0, 0)이면 용훈이는 이미 집에 있다.

출력

첫째 줄에 용훈이가 집에 도착하는 최단 시간을 출력한다. 집에 도착할 수 없으면 1-1을 출력한다.