나이트 오브 나이츠

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

요약

N x N 체스판(N은 최대 4)에 서로 공격하지 않도록 나이트를 놓아 선택한 칸 값의 합이 최대가 되도록 한다.

문제

$N \times N$ 크기의 체스판이 있다. 안즈는 이 체스판 위에 나이트를 적절하게 배치하여 최대한 많은 점수를 얻으려고 한다.

체스판의 $x$ 행 $y$ 열에 위치한 칸에 나이트를 놓는다면, $A\_{x, y}$ 점을 얻을 수 있다. 단, 서로 공격할 수 있는 두 나이트는 동시에 배치할 수 없다.

체스에서 나이트는 'L'자 형태로 이동하며, 한 번에 가로로 두 칸 이동 후 세로로 한 칸, 또는 세로로 두 칸 이동 후 가로로 한 칸 이동할 수 있다. 아래는 나이트가 이동할 수 있는 위치를 나타낸 그림이다.

나이트는 이동할 수 있는 위치에 있는 말을 공격할 수 있으며, 두 나이트가 이러한 상대적 위치에 있을 경우 서로를 공격할 수 있다.

안즈가 얻을 수 있는 점수의 최댓값을 구하시오.

첫 번째 줄에 체스판의 크기를 나타내는 $N$ 이 주어진다.

이어서 $N$ 개의 줄에 걸쳐, 정수 $N$ 개가 공백으로 구분되어 주어진다. $i$ 번째 줄의 $j$ 번째 수는 $A\_{i,j}$ 를 나타낸다.

안즈가 얻을 수 있는 점수의 최댓값을 출력한다.