#304. 【NFLSPC #1】Encryption

题目类型:通讯型 时间限制:200 ms 空间限制:256 MiB
输入文件:标准输入 输出文件:标准输出 答案检查器:文本比较

这是一道通讯题。

在混乱的学生时代,传纸条是学生们常用的通讯方式。但是,信息在传输过程中可能改变。为了保证你和你的好基友能愉快地交流,你决定使用一种加密方式和一种解密方式,来保证对方接收到的信息后即使信息改变了也能解密出原来的信息。

形式化地说,原信息是一个 $n \times m$ 的 01 矩阵,发送方需要将它加密成一个大小为 $n^\prime \times m^\prime$ 的 01 矩阵,其中 $n^\prime \leq n + 2, m^\prime \leq m + 2$。加密后的信息在传输过程中可能会按某些方式经过一系列的改变,接受方接收到的是加密信息被改变后的结果,需要将它解密成原信息。

信息的改变(即 01矩阵的改变)可能是以下几种方式的组合:

  1. 左右翻转
  2. 上下翻转
  3. 顺时针旋转 $90^\circ$
  4. 行轮换,即第一行被移到最后一行的下面
  5. 列轮换,即第一列被移到最后一列的右面

注意在通讯过程中,信息可能会经过任意多次改变,并且每次改变的方式也是任意的。

要求

本题你需要写两个程序,第一个程序实现加密过程,第二个程序实现解密过程。

两个程序的运行时间限制均为 $200\ \texttt{ms}$,空间限制为 $256\ \texttt{MB}$。


输入格式

加密程序

第一行一个正整数 $T$,表示子任务编号(参见评分标准)。

第二行两个正整数 $n$ 和 $m$ 表示原矩阵大小。

接下来 $n$ 行 $m$ 列表示你要加密的信息,每个字符是 01

解密程序

第一行一个正整数 $T$,表示子任务编号(参见评分标准)。

第二行两个正整数 $n^{\prime\prime}$ 和 $m^{\prime\prime}$ 表示经过加密和多次改变之后的矩阵大小。显然,$n^{\prime\prime}$ 和 $m^{\prime\prime}$ 满足 $$(n^{\prime\prime} = n^\prime \mathbin{\text{and}} m^{\prime\prime} = m^\prime) \mathbin{\text{or}} (n^{\prime\prime} = m^\prime \mathbin{\text{and}} m^{\prime\prime} = n^\prime).$$

接下来 $n^{\prime\prime}$ 行 $m^{\prime\prime}$ 列表示你要解密的信息,每个字符是 01

输出格式

加密程序

第一行两个整数 $n^\prime$ 和 $m^\prime$,表示加密后的矩阵大小。

接下来输出 $n^\prime$ 行 $m^\prime$ 列,表示加密后的矩阵,每个字符必须是 01

$n^\prime$ 和 $m^\prime$ 应满足 $n^\prime \leq n + 2$,$m^\prime \leq m + 2$。

解密程序

第一行两个整数 $n$ 和 $m$,表示原矩阵大小。

接下来 $n$ 行 $m$ 列表示原矩阵内容,每个字符是 01

这个矩阵应和加密程序输入的矩阵完全相同。


样例

加密程序输入
2
10 10
1000101000
0101011001
1111110101
1100101111
1001101100
0101011001
1001001101
1100011010
0001010110
1001010111

可能的加密程序输出
12 12
100010100000
010101100100
111111010100
110010111100
100110110000
010101100100
100100110100
110001101000
000101011000
100101011100
111111111111
111111111111
可能的解密程序输入
2
12 12
000001010001
001001101010
001010111111
001111010011
000011011001
001001101010
001011001001
000101100011
000110101000
001110101001
111111111111
111111111111
解密程序输出
10 10
1000101000
0101011001
1111110101
1100101111
1001101100
0101011001
1001001101
1100011010
0001010110
1001010111




评分标准

本题为子任务制。得到一个子任务的分数需要你通过这个子任务的全部测试点。

子任务编号分值限制说明
$1$$10\%$$10 \leq n, m \leq 100$保证信息在传输过程不改变
$2$$10\%$保证信息在传输过程中的改变方式只有第 $1$、$2$ 种方式
$3$$20\%$保证信息在传输过程中的改变方式只有第 $1$、$2$、$3$ 种方式
$4$$20\%$保证信息在传输过程中的改变方式只有第 $4$、$5$ 种方式
$5$$20\%$无特殊说明
$6$$20\%$$1 \leq n, m \leq 100$

$by\ \text{FizzyDavid}$