APCS Oct 2018 - f637 Q3 [Python]

本題敘述：

DF-express (深度優先圖像表示式) 是一個具有高度資料壓縮能力的四元樹表示法。雖然主要為二階黑白圖片所設計，但是透過位元平面 (bit-plane) 或是 3D 表示法，亦可用來壓縮灰階圖片。

本題中所處理的圖片為二階的黑白圖片，也就是每個像素非黑即白，沒有中間的灰色。圖片大小為 𝑛×𝑛，𝑛 是2 的冪次，也就是存在某個非負整數 𝑘 使得 𝑛 = 2𝑘。

一個 𝑛×𝑛 的黑白影像可以用下列遞迴方式編碼： 如果每一格像素都是白色，我們用0來表示； 如果每一格像素都是黑色，我們用1來表示； 否則，並非每一格像素都同色，先將影像均等劃分為四個邊長為 𝑛/2 的小正方形後，

然後表示如下： 先寫下2，之後依續接上左上、右上、左下、右下四塊的編碼。 一個壓縮後的影像會表示成一個由 0、1、2 組成的字串 𝑆。在這個問題中，根據字串 𝑆 以及影像尺寸 𝑛，請計算原始影像中有多少個像素是 1。

expression = input()
pixel = int(input())

index = [0]
pre_pixel = [pixel]

total = 0

for i in range(len(expression)):
    while index[-1] == 4:
        index.pop()
        pre_pixel.pop()
        index[-1] += 1

    if expression[i] == "0":
        index[-1] += 1
    elif expression[i] == "1":
        total += pre_pixel[-1] * pre_pixel[-1]
        index[-1] += 1
    elif expression[i] == "2":
        index.append(0)
        pre_pixel.append(pre_pixel[-1] // 2)

print(total)

本題知識：

• NaN

---

• [✔️] 程式碼如果需要可以直接使用。
• [✔️] 分享貼文請標註來源。