벌집
시간 제한2초메모리 제한128 MB
나선형으로 번호가 매겨진 육각 벌집 방을 좌표로 변환해서 두 방 사이의 최단 경로에 있는 방 번호들을 출력하는 문제입니다.
문제
지민이는 육각형 방들이 이어진 벌집 안에 있다. 각 방에는 양의 정수 번호가 하나씩 붙어 있으며, 한 방에서는 변을 공유하는 여섯 이웃 방으로 이동할 수 있다.
방 번호는 1번 방을 중심에 두고 바깥쪽으로 나선형으로 붙는다. 좌표로 설명하면 1번 방은 (0, 0)이다. 한 번 이동할 때는 (-1, 0), (0, 1), (1, 1), (1, 0), (0, -1), (-1, -1) 중 하나를 더한 좌표로 갈 수 있다.
2번부터의 번호는 다음 나선 경로를 따라 차례로 붙는다. 각 둘레 r (r >= 1)은 (-r, -r + 1)에서 시작하고, (0, 1) 방향으로 r - 1번 이동한 뒤, (1, 1), (1, 0), (0, -1), (-1, -1), (-1, 0) 방향으로 각각 r번씩 이동하며 번호를 붙인다.
현재 방 번호가 a이고 출구가 있는 방 번호가 b일 때, a에서 b까지 이동하는 최단 경로의 방 번호를 모두 출력하라.
입력
첫째 줄에 현재 방 번호 a와 출구가 있는 방 번호 b가 공백으로 구분되어 주어진다.
1 <= a, b <= 1,000,000
출력
첫째 줄에 a에서 b까지 최단거리로 이동할 때 지나는 방 번호를 순서대로 공백으로 구분해 출력한다.
최단 경로가 여러 개라면 그중 아무 것이나 출력해도 된다.