장기
시간 제한2초메모리 제한128 MB
두 대각선을 모두 피하면서 N x N 보드에 N개의 전차를 행과 열이 겹치지 않게 배치하는 순열을 구성하거나 불가능하면 -1을 출력합니다.
문제
차는 가로 또는 세로 방향으로 원하는 만큼 이동할 수 있는 말이다.
N x N 게임판에 차 N개를 놓으려고 한다. 단, 다음 두 조건을 모두 만족해야 한다.
- 같은 행 또는 같은 열에 차가 두 개 이상 놓이면 안 된다.
- 왼쪽 위에서 오른쪽 아래로 가는 대각선과 오른쪽 위에서 왼쪽 아래로 가는 대각선 위에는 차를 놓을 수 없다.
조건을 만족하는 배치가 있으면 그중 하나를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 정수 N(3 <= N <= 100,000)이 주어진다.
출력
N개의 줄에 걸쳐 출력한다. i번째 줄에는 i번째 행에 놓을 차의 열 번호를 출력한다.
조건을 만족하는 배치가 여러 개라면 아무거나 출력한다. 배치가 불가능한 경우 첫째 줄에 -1만 출력한다.