최대 점수 경로 찾기

$N \times N$ 이차원 배열 $A$가 주어진다. 각 원소는 $-100$ 이상 $100$ 이하의 정수다. 이 배열에서 $A[1][1]$부터 $A[N][N]$까지 이어지는 경로를 하나 고르는데, 다음 두 제약을 지켜야 한다.

1. 상하좌우로 인접한 칸으로만 이동한다. 대각선으로는 이동하지 못한다.
2. 한 번 방문한 칸은 다시 방문하지 못한다.

두 제약을 지키면서 $A[N][N]$에 도착하면, 그 경로에서 방문한 칸의 값을 모두 더한 값이 그 경로의 점수가 된다. 배열이 주어질 때 경로의 점수가 가장 큰 경우를 구하는 프로그램을 작성하시오.

첫째 줄에 이차원 배열의 크기 $N$이 주어진다. ($3 \le N \le 10$)

다음 $N$개 줄에는 각 줄마다 정수 $N$개가 빈 칸을 사이에 두고 주어진다. $i+1$번째 줄의 $j$번째 정수가 $A[i][j]$이며, 모든 값은 $-100$ 이상 $100$ 이하다.

첫째 줄에 경로의 점수 중 최댓값을 출력한다.