AT_abc258_b [ABC258B] Number Box

题目描述

给定一个正整数 $N$。

有一个 $N$ 行 $N$ 列的格子，每个格子的第 $i$ 行第 $j$ 列上写有数字 $A_{i,j}$。

这个格子的上下和左右是连通的。也就是说，以下条件都成立：

• 第 $i$ 列第 $1$ 行的上方格子是第 $i$ 列第 $N$ 行，第 $i$ 列第 $N$ 行的下方格子是第 $i$ 列第 $1$ 行。$(1 \leq i \leq N)$
• 第 $i$ 行第 $1$ 列的左侧格子是第 $i$ 行第 $N$ 列，第 $i$ 行第 $N$ 列的右侧格子是第 $i$ 行第 $1$ 列。$(1 \leq i \leq N)$

高桥君可以从上下左右以及斜向的 $8$ 个方向中任选一个方向，并从任意一个格子出发，按照选定的方向移动 $N-1$ 次（每次移动 $1$ 格）。

高桥君会经过 $N$ 个格子，请你求出他经过的格子上所写数字按经过顺序从左到右拼接成的整数的最大值。

输入格式

输入按以下格式从标准输入给出。

$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

输入 #1

4
1161
1119
7111
1811

输出 #1

9786

输入输出样例 #2

输入 #2

10
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111

输出 #2

1111111111

说明/提示

限制条件

• $1 \leq N \leq 10$
• $1 \leq A_{i,j} \leq 9$
• 输入均为整数。

样例解释 1

高桥君从第 $2$ 行第 $4$ 列的格子出发，向右下方移动，可以拼出 $9786$。无法拼出比 $9786$ 更大的数，因此答案为 $9786$。

样例解释 2

请注意，答案不一定能用 32 位整数类型存下。

由 ChatGPT 4.1 翻译