102581: [AtCoder]ABC258 B - Number Box

Problem Statement

You are given a positive integer $N$.

We have a grid with $N$ rows and $N$ columns, where the square at the $i$-th row from the top and $j$-th column from the left has a digit $A_{i,j}$ written on it.

Assume that the upper and lower edges of this grid are connected, as well as the left and right edges. In other words, all of the following holds.

• $(N,i)$ is just above $(1,i)$, and $(1,i)$ is just below $(N,i)$. $(1\le i\le N)$.
• $(i,N)$ is just to the left of $(i,1)$, and $(i,1)$ is just to the right of $(i,N)$. $(1\le i\le N)$.

Takahashi will first choose one of the following eight directions: up, down, left, right, and the four diagonal directions. Then, he will start on a square of his choice and repeat moving one square in the chosen direction $N-1$ times.

In this process, Takahashi visits $N$ squares. Find the greatest possible value of the integer that is obtained by arranging the digits written on the squares visited by Takahashi from left to right in the order visited by him.

Constraints

• $1 \le N \le 10$
• $1 \le A_{i,j} \le 9$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$
$A_{1,1}A_{1,2}\dots A_{1,N}$
$A_{2,1}A_{2,2}\dots A_{2,N}$
$\vdots$
$A_{N,1}A_{N,2}\dots A_{N,N}$

Output

Print the answer.

Sample Input 1

4
1161
1119
7111
1811

Sample Output 1

9786

If Takahashi starts on the square at the $2$-nd row from the top and $4$-th column from the left and goes down and to the right, the integer obtained by arranging the digits written on the visited squares will be $9786$. It is impossible to make a value greater than $9786$, so the answer is $9786$.

Sample Input 2

10
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111

Sample Output 2

1111111111

Note that the answer may not fit into a 32-bit integer.

问题描述

你将得到一个正整数 N。

我们有一个 N 行 N 列的网格，其中在距离顶部第 i 行、距离左侧第 j 列的方格上写着一个数字 A_{i,j}。

假设这个网格的上边缘和下边缘是相连的，左边缘和右边缘也是相连的。换句话说，以下所有条件都成立。

• (N,i) 在 (1,i) 的正上方，(1,i) 在 (N,i) 的正下方。 $(1\le i\le N)$。
• (i,N) 在 (i,1) 的正左侧，(i,1) 在 (i,N) 的正右侧。 $(1\le i\le N)$。

高桥首先将从以下八个方向中选择一个：上、下、左、右和四个对角线方向。然后，他将从他选择的方格开始，并按选择的方向重复移动一个方格 N-1 次。

在这个过程中，高桥会访问 N 个方格。找出按高桥访问顺序从左到右排列的方格上的数字组成的整数的最大可能值。

约束

• $1 \le N \le 10$
• $1 \le A_{i,j} \le 9$
• 输入中的所有值都是整数。

输入

输入以以下格式从标准输入给出：

$N$
$A_{1,1}A_{1,2}\dots A_{1,N}$
$A_{2,1}A_{2,2}\dots A_{2,N}$
$\vdots$
$A_{N,1}A_{N,2}\dots A_{N,N}$

输出

打印答案。

样例输入 1

4
1161
1119
7111
1811

样例输出 1

9786

如果高桥从距离顶部第 2 行、距离左侧第 4 列的方格开始，向下并向右走，按高桥访问的方格上的数字排列的整数将为 9786。 无法使值大于 9786，因此答案为 9786。

样例输入 2

10
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111

样例输出 2

1111111111

请注意，答案可能不适合 32 位整数。