压缩二维码

OPPO 笔试真题 · 2023 秋招 · 移动端岗

判题请到牛客原题提交。

题目描述

小欧的二维码转换服务上线了！只需要发送一个字符串，服务器就会把他转换成一个二维码发送给客户端。二维码是一个为 ${2^n*2^n}$ 的方格子，里面每个 $1*1$ 的格子都有黑或者白两种颜色。然而，没过多久，小欧的服务器就崩溃了。经过检查，小欧发现，服务器会生成一张二维码的图片，发送给客户端，而传输图片的流量大小过大，导致服务器瘫痪。聪明的小欧知道只有黑白格的二维码可以用比特位 $0$ 和 $1$ 来编码，编码后的传输效率远远大于图片。

小欧发明了一种编码方式：用 ${2^n*2^n}$ 长度的二进制串来表示一个边长为 $n$ 的二维码。他会逐行扫描该二维码，并且把扫描到的内容变成 $0,1$ 比特流，其中 $0$ 代表白色，$1$ 代表黑色。

现在给你一张二维码图，请你把他转换成比特流。

输入格式

第一行一个数 $n\ (1\leq n\leq 10)$ 。

接下来 $2^n$ 行，每行 $2^n$ 个字符，代表该二维码图形。其中 $.$ 代表白色，$\#$ 代表黑色。

输出格式

$\frac{ {2^n*2^n}}{4}$ 个整数，代表转换后的比特流。每个整数为4位比特位所组成的二进制数的值。

示例

示例 1

输入：

1
.#
#.

输出：

6

示例 2

输入：

2
.##.
#..#
##..
...#

输出：

6 9 12 1

说明：

逐行扫描后，得到的01比特流为：0110100111000001。

将4个比特位合成为一个整数，得到 6(0110) 9(1001) 12(1100) 1(0001)。

示例 3

输入：

3
#.##.#.#
#..#.##.
###.#.##
####.##.
##..#...
.##.#.#.
######.#
...##.#.

输出：

11 5 9 6 14 11 15 6 12 8 6 10 15 13 1 10

---

解题思路

第一步：理解问题本质

二维码是边长为 side = 2^n 的正方形。「逐行扫描」的意思是行优先：
先读完第 1 行从左到右，再读第 2 行，一直到最后一行。把 '.' 记 0、'#' 记 1，
就得到一条长度为 side × side 的比特流。

side = 2^n 在 n >= 1 时是偶数，所以 side² 一定能被 4 整除 ——
题目要的「每 4 位合成一个整数」不会有剩余位数。

第二步：4 位比特怎么变成整数

四位 b1 b2 b3 b4 的十进制值是

b1 * 8 + b2 * 4 + b3 * 2 + b4

也就是把这 4 个字符当成一个二进制串解析。int(串, 2) 一行就能完成，
不必自己乘权重。

第三步：规模够小，直接模拟

n <= 10，side <= 1024，最多 1024 × 1024 = 1,048,576 个比特。
拼串 + 每隔 4 位切一刀，O(4^n) 的时间完全够用，不需要任何压缩技巧。

---

完整代码实现

import sys


def solve() -> None:
    """按行优先拼比特串，每 4 位转一个整数"""
    data = sys.stdin.read().split()
    if not data:
        return

    n = int(data[0])
    side = 1 << n
    rows = data[1:1 + side]

    # 一行一行拼，'.' -> 0，'#' -> 1
    bits = "".join("1" if ch == "#" else "0" for row in rows for ch in row)

    out = [str(int(bits[i:i + 4], 2)) for i in range(0, len(bits), 4)]
    sys.stdout.write(" ".join(out) + "\n")


if __name__ == "__main__":
    solve()

---

示例推演

示例 1

.#
#.

行优先读出 0 1、1 0，拼成 0110，int("0110", 2) = 6，输出 6。

示例 2

行	图形	比特
1	.##.	0110
2	#..#	1001
3	##..	1100
4	...#	0001

拼起来是 0110 1001 1100 0001，按 4 位切成 4 段，分别解析为
6、9、12、1，输出 6 9 12 1 —— 与说明里给出的比特流完全一致。

示例 3

n = 3，边长 8，共 64 个比特、16 个整数。按同样的方式逐行读出后再 4 位一合，
得到 11 5 9 6 14 11 15 6 12 8 6 10 15 13 1 10。

---

复杂度分析

解法	时间复杂度	空间复杂度	说明
逐行拼比特串后 4 位一合	O(4^n)	O(4^n)	推荐，n = 10 时约 100 万字符
边读边累积（4 位一组直接算出）	O(4^n)	O(2^n)	省掉整条比特串，思路相同

---

易错点总结

1. 扫描顺序搞错

是行优先（一行读完再读下一行），不是列优先（一列读完再读下一列）。
按列读的话，示例 2 的前两组会变成 . # # . 与 # . . #，拼出来的比特流完全不同。

2. 4 位的高低位写反

0110 是 6，不是 9。最左边那一位权重最大（8），最右边权重最小（1）。
用 int(s, 2) 可以避免手写权重时出错。

3. 输出格式

所有整数用空格分隔，输出在一行里；最后一个数后面不需要额外空格
（" ".join 天然满足）。

4. 逐行用 input() 读

n = 10 时有 1024 行、每行 1024 个字符。用 sys.stdin.read().split() 一次性读完
更省事，而且 '.'、'#' 里没有空格，切分后正好是「n + 行内容」这种扁平结构。

5. n = 1 时的边界

此时只有 4 个比特，输出一个整数，不要因为「循环从 0 到 4」之类的写法漏掉或多输出。

---

扩展思考

• 如果要求「每 8 位一组」（一个字节一个数），把切片长度从 4 改成 8 即可，
  代码结构完全不变。
• 如果二维码的边长是任意整数（不保证是 2 的幂），末尾可能需要补零对齐 ——
  那就要额外处理「不足 4 位」的尾巴。
• 真正的二维码压缩远比这复杂：它利用定位图案、掩码和纠错码，
  而不是简单地把黑白格按位打包。本题只是「位打包」这一层的模拟。