J1 实践-1 数字盒子

题目描述

有一个包含 $N$ 行和 $N$ 列的数字盒子，其中从顶部开始的第 $i$ 行和从左侧开始的第 $j$ 列的方格上，有一个数字 $A_{i,j}$（保证是一位数）。 该数字网格的上边缘和下边缘循环连接，左边缘和右边缘也是连接的。 换句话说，以下所有条件都成立。 1、$(N,i)$ 刚好高于 $(1,i)$，$(1,i)$ 刚好低于$(N,i)$ $(1\le i\le N)$。 2、$(i,N)$ 正好位于 $(i,1)$ 的左侧，$(i,1)$ 正好位于$(i,N)$ 的右侧 。

喵喵可以在网格中，任选一个位置作为起点，并且选择八个方向之一（上、下、左、右和四个对角方向），然后，一直移动 $N-1$ 个方格。

在这个过程中，喵喵共访问了 $N$ 个方格。 请问，她如何选择初始位置和行进方向，可以使得走过格子的数字，拼接后最大？

输入格式

共 $N+1$ 行。

第一行一个整数 $N$，表示网格的行高和列宽。 接下来 $N$ 行，每行 $N$ 个整数，表示对应的方格上的数字（数字之间没有空格）。

输出格式

一行一个整数，表示喵喵访问了 $N$ 个方格后找到整数，拼接后的最大可能值。

样例输入

4
1161
1119
7111
1811

样例输出

9786

样例1解析

如果喵喵从第 $2$ 行，第 $4$ 列的方格开始，向右下移动，则通过排列所访问的方格上的数字获得的整数将为 9786。

数据范围

对于 $100 \%$​ 的数据：$1 \le N \le 10$，$1 \le A_{i,j} \le 9$。