数字接龙【修正数据范围】

题目描述

本题目前未找到任何做法（在不进行特判的情况下）进行有效剪枝通过 $n=10，k=1$ 的数据。因此评测数据约定不会存在这样的极限数据，结果仅供参考。

小蓝最近迷上了一款名为《数字接龙》的迷宫游戏，游戏在一个大小为$N × N$ 的格子棋盘上展开，其中每一个格子处都有着一个 $0 . . . K − 1$ 之间的整数。游戏规则如下：

1. 从左上角 $(0, 0)$ 处出发，目标是到达右下角 $(N − 1, N − 1)$ 处的格子，每一步可以选择沿着水平/垂直/对角线方向移动到下一个格子。

2. 对于路径经过的棋盘格子，按照经过的格子顺序，上面的数字组成的序列要满足：$0, 1, 2, . . . , K − 1, 0, 1, 2, . . . , K − 1, 0, 1, 2 . . .$ 。

3. 途中需要对棋盘上的每个格子恰好都经过一次（仅一次）。

4. 路径中不可以出现交叉的线路。例如之前有从 $(0, 0)$ 移动到 $(1, 1)$，那么再从 $(1, 0)$ 移动到 $(0, 1)$ 线路就会交叉。

为了方便表示，我们对可以行进的所有八个方向进行了数字编号，如下图2 所示；因此行进路径可以用一个包含 $0 . . . 7$ 之间的数字字符串表示，如下图 1是一个迷宫示例，它所对应的答案就是：$41255214$。 现在请你帮小蓝规划出一条行进路径并将其输出。如果有多条路径，输出字典序最小的那一个；如果不存在任何一条路径，则输出 $−1$。

输入格式

第一行包含两个整数 $N、K$。接下来输入 $N$ 行，每行 $N$ 个整数表示棋盘格子上的数字。

输出格式

输出一行表示答案。如果存在答案输出路径，否则输出 $−1$。

样例 #1

样例输入 #1

3 3
0 2 0
1 1 1
2 0 2

样例输出 #1

41255214

提示

【样例说明】行进路径如图 1 所示。 【评测用例规模与约定】 对于 $80\%$ 的评测用例：$1 ≤ N ≤ 5$。 对于 $100\%$ 的评测用例：$1 ≤ N ≤ 10$，$1 ≤ K ≤ 10$。

【提示】本题的评测数据约定不会存在 $n=10，k=1$ 的极限数据，结果仅供参考。