Score : $200$ points

问题描述

给定一个正整数 $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$ 个方格。请找出按照高桥访问顺序，将他访问过的方格上的数字从左到右排列后所能得到的最大整数值。

以上为通义千问 qwen-max 翻译，仅供参考。

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.

update @ 2024/3/10 10:57:11