현욱은 옛날 자신에게 알고리즘을 가르쳐 준 스승님이 어느 신비로운 밀림 속 나무 아래에서 수행 중이라는 사실을 전해 들었다.
이 무한한 넓이의 밀림에는 모든 격자점(x, y 좌표가 모두 정수인 위치)마다 완전히 똑같은 모양의 나무가 한 그루씩 심어져 있고, 현욱의 스승은 그 중 (M,N) 좌표의 나무 아래에서 수행을 하고 있다.
이 밀림에는 또 다른 특징이 있는데, 어떤 나무 아래에서 볼 수 있는 다른 나무로 순간이동을 할 수 있다는 것이다. 어떤 나무 아래에서 다른 나무를 보려면, 그 두 나무의 좌표를 잇는 직선을 그었을 때 중간에 다른 나무가 존재하지 않아야 한다.
예를 들어, 현욱이 (0, 0) 위치에 있을 때 (1, 1) 위치에 있는 나무 혹은 (1,2) 위치에 있는 나무는 볼 수 있기 때문에 바로 순간이동 할 수 있다. 하지만 (2, 4) 위치에 있는 나무는 (1, 2) 위치에 있는 나무에 가려 보이지 않으므로 바로 순간이동 할 수 없다.
현욱은 수행을 돕기 위해 스승님이 있는 곳으로 가려고 한다. 하지만 밀림의 신비로운 기운으로 인해 나무 사이를 걸어서 이동하는 것은 위험할 수 있어서, 현욱은 순간이동만 이용해서 (M, N) 위치로 이동할 것이다. 또, 순간이동은 할 때마다 멀미가 심하게 나기 때문에 현욱은 최대한 적은 횟수만큼만 순간이동을 사용해서 (M, N) 위치로 이동하려고 한다.
이 밀림에 들어오는 모든 사람은 저절로 (0,0) 위치에 있는 나무 밑으로 이동하게 된다. 현욱을 도와 (0,0) 위치의 나무 아래에서 (M, N) 위치의 나무 아래로 이동하는 데 필요한 최소 순간이동 횟수를 구해보자.
cho.sh