【題目敘述】https://zerojudge.tw/ShowProblem?problemid=f637
【題目敘述】https://judge.tcirc.tw/ShowProblem?problemid=d005
【解題想法】遞迴 (recursion)
- 讀入測資，存於string s，再逐一判斷每個字元。
- 字元’0’：沒有黑色格子。
- 字元’1’：黑色格子的數目為當時的寬度 w * w。
- 字元’2’：處理四個更小的方格（左上、右上、左下、右下），但寬度變成原值的一半。
#include <iostream>
using namespace std;
int width, idx;
string s;
int func(int w){
idx++;
if (s[idx] == '0') return 0;
else if (s[idx] == '1') return w * w;
else {
int ret = 0;
for (int i = 0; i < 4; i++){
ret += func(w/2);
}
return ret;
}
}
int main() {
cin >> s;
cin >> width;
idx = -1;
cout << func(width) << "\n";
}
Python code (credit: Amy Chou)
def func(w):
global idx
idx += 1
if s[idx] == '0':
return 0
elif s[idx] == '1':
return w * w
else:
ret = 0
for _ in range(4):
ret += func(w//2)
return ret
# main program
s = input()
width = int(input())
idx = -1
print(func(width))