1. 问题重述
给定行数 R 和列数 C,以及一个由大写字母和空格组成的字符串。
每个字符编码为 5 位二进制:空格 → 00000,A → 00001,B → 00010,…,Z → 11010(即 26 的二进制)。
所有字符的二进制位依次拼接成一个长二进制串。
这个长串的长度可能小于 RC(因为题目保证字符串长度 ≤ (RC)/5,所以二进制位数 ≤ RC),不足的部分用 0 补足,使总位数恰好等于 RC。
然后将这 R*C 个二进制位按顺时针螺旋顺序填入一个 R 行 C 列的矩阵中(从左上角开始,向右、向下、向左、向上,依次循环)。
最后按行优先顺序输出矩阵中的所有数字(即从左到右、从上到下输出),形成最终的加密串。
2. 字符 → 5 位二进制
映射规则
空格 → 0
A → 1,B → 2,…,Z → 26
转换方法
对每个字符 ch:
计算数值 val:
如果 ch == ' ',val = 0
否则 val = ch - 'A' + 1
将 val 转为 5 位二进制,不足 5 位前面补 0。
例如:
0 → 00000
1 → 00001
26 → 11010
在代码中,常用循环从高位到低位依次取出每一位:
所有字符的位依次追加到一个动态数组 bits 中。
3. 补零到矩阵大小
记原始二进制串长度为 len,矩阵总格数为 total = R * C。因为题目保证 len ≤ total,所以只需在 bits 尾部追加 (total - len) 个 0,使得 bits.size() == total。
这一步确保了矩阵能被完整填充。
4. 顺时针螺旋填充
现在有一个长度为 total 的二进制序列,需要按顺时针螺旋顺序填入 R × C 矩阵。
螺旋顺序
从矩阵的左上角 (0,0) 开始:
向右走,填满当前最上面一行(从左边界到右边界)。
向下走,填满当前最右边一列(从上边界到下边界)。
向左走,填满当前最下面一行(从右边界到左边界)。
向上走,填满当前最左边一列(从下边界到上边界)。
重复上述过程,每走完一个方向就缩小对应的边界,直到所有元素填完。
边界控制
定义四个变量:
top:当前未填充的最上行索引(初始 0)
bottom:当前未填充的最下行索引(初始 R-1)
left:当前未填充的最左列索引(初始 0)
right:当前未填充的最右列索引(初始 C-1)
每一次循环执行四步(但每一步之前都要检查是否还有未填的元素,因为可能在某一步已经全部填完):
每步之前的 idx < total 检查是为了防止在已经填完的情况下继续不必要的操作(例如矩阵为 1×1 时)。
5. 按行输出
填充完成后,矩阵 mat 中已经包含了正确的位。按照行优先顺序(第一行从左到右,第二行从左到右,……)依次输出每个数字(0 或 1),中间不加空格或换行,最终形成一个长字符串。
6. 关键注意事项
读取输入:字符串可能包含空格,因此不能用 cin >> s 直接读,而应使用 getline。常见的处理方式是先用 cin >> R >> C,然后 cin.get() 吃掉分隔符,再用 getline(cin, s) 读取剩余整行。如果字符串前有多余空格(题目保证只有一个),也可手动去掉第一个空格。
补零的原因:题目要求最终输出长度为 R*C 的二进制串,因此无论原始二进制串多短,都必须补足。
螺旋填充的方向:从题目给出的样例来看(ACM,4×4),若直接按顺序填充则输出为 0000110100101100,这正是顺时针螺旋的结果。因此必须采用螺旋填充,而不是简单的逐行填充。
7. 样例验证
以输入 4 4 ACM 为例:
A → 00001,C → 00011,M → 01101
原始串:00001 00011 01101 → 000010001101101(15 位)
矩阵总格数 4×4 = 16,补 1 个 0 → 0000100011011010(16 位)
顺时针螺旋填入 4×4 矩阵,得到:
按行输出:0000110100101100,与题目输出完全一致。
8. 时间复杂度与空间复杂度
时间复杂度:O(R×C),只需一次遍历填充和一次输出。
空间复杂度:O(R×C),用于存储矩阵和二进制数组。