题目内容

给定一个 $M \times N$ 的矩形网格（$M \times N \le 100$），每个格子按照行优先顺序（从左到右，从上到下）依次填充正整数，起始值为 $1$。例如对于 $3 \times 3$ 的网格：格子 $(0,0) = 1$，格子 $(0,1) = 2$，格子 $(0,2) = 3$，格子 $(1,0) = 4$，依此类推。

现输入一个整数序列，需判断该序列是否能构成网格中的一条有效解锁路径，需满足以下条件：

1. 输入的整数序列的任意两个相邻的数字，在对应的网格中需要相邻。 网格中任意一个格子，其相邻的格子包括其上、下、左、右、左上、右上、左下、右下共 $8$ 个方向的格子（若存在）。

注：数字 $2$ 的相邻格子有 $1$、$3$、$4$、$5$、$6$；

注：数字 $5$ 的相邻格子有 $1$、$2$、$3$、$4$、$6$、$7$、$8$、$9$。

2. 序列中任意两个相邻数字组成的路径不能重复。

这里的路径重复是指包括正向和反向的。

以该网格为例，假如序列中出现了路径 $(2,5)$，后续不能再出现路径 $(2,5)$ 和 $(5,2)$ 了。

举例1：:整数序列 {$1,2,3,5,7,8$} 满足解锁条件，因为格子 $1$ 和格子 $2$，格子 $2$ 和格子 $3$，格子 $3$ 和格子 $5$，格子 $5$ 和格子 $7$，格子 $7$ 和格子 $8$ 相邻。

举例2：整数序列 {$1,2,3,4,7$} 不满足解锁条件，因为格子 $3$ 和格子 $4$ 不相邻（标记 $1$）

举例3：整数序列 {$1,2,5,8,5,6$} 不满足解锁条件，因为格子 $5$ 和格子 $8$ 构成的边与格子 $8$ 与格子 $5$ 构成的边重复了（标记 $1$ 和标记 $2$）

输入描述

• 矩阵网格的行数 $m$（$1 \le m \le 100$）
• 矩阵网格的列数 $n$（$1 \le n \le 100$）
• 待解锁的序列个数 $n$（$1 \le n \le 5$）
• 待解锁的序列 $sequence$（$1 \le \text{sequence} \le m \times n$，$sequence$ $size[]$ 大于 $1$）

输出描述

• 输出所有可解锁的序列。
• 多个可解锁的序列按照输入的序列顺序输出，每个序列占一行。
• 如果一个序列都没有，返回 $false$。

样例1

输入

3
3
4
1,2,5,8,5,6
1,2,3,4,7
1,2,3,5,7,8
1,2,3,5,7,4

输出

1,2,3,5,7,8
1,2,3,5,7,4

说明

有两个可解锁的序列，最终输出可解锁的序列。

$1,2,3,5,7,8$

$1,2,3,5,7,4$

样例2

输入

3
3
3
1,2,5,8,5,6
1,2,3,4,7
1,2,3,5,7,8

输出

1,2,3,5,7,8

说明

$3$ // 表示 $3$ 行

$3$ // 表示 $3$ 列

$3$ // 表示有 $3$ 个待解锁的序列

整数序列 {$1,2,5,8,5,6$} 不满足解锁条件

整数序列 {$1,2,3,4,7$} 不满足解锁条件

整数序列 {$1,2,3,5,7,8} 满足解锁条件，因为格子 $1$ 和格子 $2$、格子 $2$ 和格子 $3$、格子 $3$ 和格子 $5$、格子 $5$ 和格子 $7$、格子 $7$ 和格子 $8$ 均相邻。

因此，最终输出可解锁的序列 $1,2,3,5,7,8$

样例3

输入

3
3
1
1,2,5,8,5,6
1,2,3,4,7

输出

false

说明

整数序列 {$1,2,5,8,5,6$} 不满足解锁条件。

整数序列 {$1,2,3,4,7$} 不满足解锁条件，因为格子 $3$ 和格子 $4$ 不相邻。

由于这 $2$ 个序列都不满足解锁条件，因此输出 $false$。

样例4

输入

3
3
2
1,2,5,8,5,6
1,2,3,5,7,8

输出

1,2,3,5,7,8

说明

$3$ // 表示 $3$ 行

$3$ // 表示 $3$ 列

$3$ // 表示有 $2$ 个序列待判断是否可解锁

$1,2,5,8,5,6$ // 表示待解锁的整数序列

$1,2,3,5,7,8$ // 表示待解锁的整数序列

整数序列 {$1,2,5,8,5,6$} 不满足解锁条件，因为格子 $5$ 和格子 $8$ 构成的边与格子 $8$ 和格子 $5$ 构成的边重复了。

整数序列 $1,2,3,5,7,8$ 满足解锁条件。

故最终输出 $1,2,3,5,7,8$