당신은 N x N 짜리 체스보드와 Kingknight라는 특수한 말을 하나 가지고 있다. Kingknight는 한 턴에 King이 움직일 수 있는 범위와 Knight가 움직일 수 있는 범위로 이동할 수 있다. 즉 아래 그림에서 K의 위치에 있는 Kingknight는 파란색으로 색칠된 위치로 이동할 수 있다. 단 Kingknight는 체스보드 밖으로 벗어날 수는 없다.

  

보드의 크기와 시작좌표 목표좌표가 주어졌을 때 시작좌표로부터 정확히 numMoves번 이동하여 목표좌표로 도달할 수 있는 경우의 수를 계산하여라. 시작좌표와 목표좌표는 언제나 보드를 벗어나지 않는다. 경우의 수는 항상 2³¹-1보다 크지 않다고 가정해도 좋다. (즉 2³¹이상의 경우의 수를 가지는 입력 데이터는 들어오지 않는다.)

입력은 한 줄로 이루어지며 체스보드의 크기 N 시작 좌표 (x, y) 목표 좌표 (x, y) numMoves가 차례대로 한 줄에 입력된다.
체스보드의 크기 N은 3 이상 100 이하의 자연수이다.
모든 x y좌표는 0 이상 N-1이하의 정수이고 numMoves는 1 이상 50 이하의 자연수이다.

입력에 대해서 시작좌표에서 numMoves번 이동하여 목표좌표로 도달할 수 있는 경우의 수를 출력하시오.

3 0 0 1 0 1

1

• 목록