나이트의 이동

시간 제한1초메모리 제한1024 MB

요약
N x N 격자판에서 한 번의 연산을 나이트 이동 두 번으로 정의할 때, 시작 칸에서 연산을 반복해 도달할 수 있는 칸의 수를 구한다.
난이도

보통10점 중 7점

유형
수학, 그래프, BFS, 구현
정답자
아직 제출이 없습니다

문제

크기가 N×NN \times N인 격자판이 있다. 가장 왼쪽 윗 칸을 11행 11열, 가장 오른쪽 아래 칸을 NN행 NN열이라고 하자.

  • 나이트는 체스의 나이트와 같은 규칙, 즉 한 방향으로 두 칸 움직인 후 수직 방향으로 한 칸 움직이는 형태의 이동을 한다.
  • 하나의 연산을 "나이트가 연속으로 두 번 이동한 후 멈추는 것"이라고 정의한다.
  • 이 연산을 무한히 반복 가능하며, 각 연산을 시작하는 위치는 직전 연산이 끝난 위치가 된다.

다음은 33행 22열에서 시작한 나이트가 한 번 연산을 진행했을 때의 결과로 나타날 수 있는 예시이다. 나이트는 33행 22열에서 22행 33열로 이동하였다.

나이트는 특정 시작 위치 RR행 CC열에서 연산을 반복한다.

연산이 끝났을 때 나이트가 위치할 수 있는 칸의 개수는 몇 개일까?

단, 연산을 전혀 수행하지 않은 초기 시점, 즉 시작 시점 자체도 연산이 끝난 상태로 간주할 수 있다.

입력

첫째 줄에 격자판의 크기 NN이 주어진다. (3≤N≤100,000)(3 \le N \le 100\\,000)

둘째 줄에 나이트의 시작 위치 R,CR, C가 공백을 두고 주어진다. (1≤R,C≤N)(1 \le R, C \le N)

출력

첫째 줄에 연산이 끝났을 때 나이트가 위치할 수 있는 칸의 개수를 출력한다.

예제2

  1. 예제 1

    입력
    3
    3 2
    
    예상 출력
    4
    
  2. 예제 2

    입력
    3
    2 2
    
    예상 출력
    1