쉬운 체스
시간 제한2초메모리 제한512 MB
8x8 체스판에서 룩을 정확히 n번 움직여 a1에서 h8까지 이동하되, 방문하는 n+1개 칸이 모두 달라야 하는 경로를 찾는다.
문제
Elma는 체스 기물을 배우고 있다.
그녀는 룩이 가로 또는 세로로만 움직일 수 있다는 것을 배웠다. 룩의 움직임에 대한 이해를 돕기 위해 Elma의 할머니는 Elma에게 8 × 8 체스판을 주고, 룩을 a1에서 h8까지 정확히 n번의 이동으로 옮기되 방문하는 모든 칸이 서로 다르도록 하는 방법을 찾으라고 했다.
방문한 칸은 시작 칸 a1과 룩이 이동 후 도착하는 각 칸이다.
입력
입력은 정수 n 하나로 이루어진다. (2 ≤ n ≤ 63) 이는 원하는 이동 횟수이다.
출력
룩이 방문하는 n+1개의 칸을 방문 순서대로 공백으로 구분하여 출력한다. 모든 칸은 서로 달라야 한다. 목록은 a1으로 시작하고 h8로 끝나야 한다. 답은 항상 존재한다.