# APCS實作題2018年10月第3題：DF-expression

> 日期：2024年8月20日
> 作者：王一哲
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=f637)

## 題目

### 問題描述

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

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

一個 $n \times n$ 的黑白影像可以用下列遞迴方式編碼：

如果每一格像素都是白色，我們用 $0$ 來表示；如果每一格像素都是黑色，我們用 $1$ 來表示；否則，並非每一格像素都同色，先將影像均等劃分為四個邊長為 $n/2$ 的小正方形後，然後表示如下：先寫下 $2$，之後依續接上左上、右上、左下、右下四塊的編碼。

一個壓縮後的影像會表示成一個由 $0$、$1$、$2$ 組成的字串 $S$。在這個問題中，根據字串 $S$ 以及影像尺寸 $n$，請計算原始影像中有多少個像素是 $1$。
<br />

### 輸入說明

測試資料有兩行，第一行是影像的 DF-expression $S$，是由連續的 $0$、$1$、$2$ 組成的字串，字串長度小於 $1,100,000$。第二行為正整數 $n$，$1 \leq n \leq 1024$，代表影像的大小為 $n \times n$，其中 $n$ 必為 $2$ 的冪次。
<br />

### 輸出格式

請輸出該影像中有多少像素是 $1$。
<br />

### 範例輸入1

2200101020110
4

### 範例輸出1

7

### 範例輸入2

2020020100010
8

### 範例輸出2

17

<br /><br />

## Python 程式碼

費時最久約為 1 s，使用記憶體最多約為 6.9 MB，通過測試。

S = input()  # 讀取字串 S
n = int(input())  # 讀取維度 n
k = 0  # 平分 k 次
ans = 0  # 1 的數量
count = [0]  # 每一層已檢查過的格子象限數量，加到 4 時跳回上一層
for c in S:  # 依序由 S 取出字元 c
    while count[-1] == 4:  # 如果 count 最後一位等於 4 繼續執行
        count.pop()  # 移除最後一位
        k -= 1  # k 減 1，回上一層
        n *= 2  # n 乘以 2，回上一層
        count[-1] += 1  # 上一層檢查過的象限數量加 1
    if c == '2':  # 如果 c 是 2
        n //= 2  # n 除以 2
        k += 1  # k 加 1，向下一層
        count.append(0)  # count 加一層
    elif c == '1':  # 如果 c 是 1
        ans += n*n  # 更新 1 的數量，加上 n*n
        count[-1] += 1  # 已檢查的象限數量加 1
    elif c == '0':  # 如果 c 是 0
        count[-1] += 1  # 已檢查的象限數量加 1
    #print("c = {:s}, k = {:d}, n = {:d}, ans = {:d}, count = {:}".format(c, k, n, ans, count))
print(ans)  # 印出答案

<br /><br />

## C++ 程式碼

費時最久約為 12 ms，使用記憶體最多約為 3.5 MB，通過測試。

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);  // 加速
    string S; cin >> S;  // 讀取字串 S
    int n; cin >> n;  // 讀取維度 n
    int k = 0, ans = 0;  // 平分 k 次，1 的數量
    vector<int> count = {0};  // 每一層已檢查過的格子象限數量，加到 4 時跳回上一層
    for(char c : S) {  // 依序由 S 取出字元 c
        while(count.back() == 4) {  // 如果 count 最後一位等於 4 繼續執行
            count.pop_back();  // 移除最後一位
            k--;  // k 減 1，回上一層
            n *= 2;  // n 乘以 2，回上一層
            count[count.size()-1]++;  // 上一層檢查過的象限數量加 1
        }
        
        if (c == '2') {  // 如果 c 是 2
            n /= 2;  // n 除以 2
            k++;  // k 加 1，向下一層
            count.push_back(0);  // count 加一層
        } else if (c == '1') {  // 如果 c 是 1
            ans += n*n;  // 更新 1 的數量，加上 n*n
            count[count.size()-1]++;  // 已檢查的象限數量加 1
        } else if (c == '0') {  // 如果 c 是 0
            count[count.size()-1]++;  // 已檢查的象限數量加 1
        }
    }
    cout << ans << "\n";  // 印出答案
    return 0;
}

<br /><br />

---

###### tags:`APCS`、`Python`、`C++`