조이는 쉬는시간을 즐기기 위해 n행 m열로 놓여있는 책상 위를 뛰어다니고 있다.

조이가 책상 위를 뛰어다니는 데에는 자신만의 규칙이 있다. 먼저 한 책상 위로 올라가 뛰어갈 방향을 정한다.

그 뒤, 조이는

(1) 바라보는 방향으로 뛰어가던가,

(2) 바라보는 방향을 90도만큼 회전할 수 있다.

방향은 상하좌우만 가능하다.

목표는 모든 책상을 한 번 이상 지나는 것이다.

조이는 책상을 뛰어다닐 때, 방향을 바꾸는 것이 너무 힘들었다. 그

래서 방향을 바꾸는 횟수를 최소로 하는 방법을 찾아보기로 했다.

하지만, 조이는 횟수의 최솟값을 알 수 없었다.

조이를 도와 모든 책상을 한 번 이상 지나면서, 방향을 바꾸는 횟수의 최솟값을 구해주자.

쉬는 시간 timer 1s memory 256MB

쉬는 시간 1s 256MB