# APCS實作題2024年6月第2題：電子畫布

> 日期：2024年7月2日
> 作者：王一哲
> 題目來源：2024年6月實作題第2題
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=o077)

## 題目

### 問題描述

有一個 $H \times W$ 的電子畫布，一開始數值都是 $0$ 代表未填色，接下來請模擬 $N$ 次畫筆操作。

每次畫筆操作為選一個座標 $(r, c)$ 停留 $t$ 秒，他會將曼哈頓距離 $\leq t$ 的區塊染上顏色 $x$。若有多個顏色重複填到相同區塊，顏色的數值會累加起來。

請輸出 $N$ 次操作後的畫布狀態。

### 輸入說明

第一行輸入三個正整數 $H, W, N ~(1 \leq H, W \leq 20,~ 1 \leq N \leq 100)$。

接下來有 $N$ 行，每一行有四個整數 $r, c, t, x ~(0 \leq r < H,~ 0 \leq c < W,~ 0 \leq t \leq 20,~ 1 \leq x \leq 10)$
。

子題分數：
- 60%：$H=5$。
- 40%：無限制。
<br />

### 輸出格式

輸出畫布做 $N$ 次畫筆操作後的狀態。

<br />

### 範例輸入1

1 20 3
0 13 5 7
0 6 4 4
0 13 12 6

### 範例輸出1

0 6 10 10 10 10 10 10 17 17 17 13 13 13 13 13 13 13 13 6

### 範例輸入2

6 7 3
3 2 2 1
1 6 1 2
1 3 2 5

### 範例輸出2

0 0 5 5 5 0 2
0 5 6 5 5 7 2
0 1 6 6 5 0 2
1 1 1 6 1 0 0
0 1 1 1 0 0 0
0 0 1 0 0 0 0

<br />

## Python 程式碼

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

H, W, N = map(int, input().split())  # 讀取 H, W, N
canvas = [[0]*W for _ in range(H)]  # 表示畫布狀態的 H*W 的二維串列
for _ in range(N):  # 執行N次
    r, c, t, x = map(int, input().split())  # 讀取 r, c, t, x
    for nr in range(max(0, r-t), min(H, r+t+1)):  # nr 的範圍為 0 或 (r-t) ~ (H-1) 或 (r+t)
        for nc in range(max(0, c-t), min(W, c+t+1)):  # nc 的範圍為 0 或 (c-t) ~ (W-1) 或 (c+t)
            if abs(nr-r) + abs(nc-c) <= t:  # 如果 (nr, nc) 與 (r, c) 的曼哈頓距離小於等於 t
               canvas[nr][nc] += x  # 更新畫布 (nr, nc) 的值

for row in canvas: print(*row)  # 利用 for 迴圈與開箱運算子印出答案

<br /><br />

## C++ 程式碼

### 寫法1，使用 array

費時最久約為 3 ms，使用記憶體最多約為 324 kB，通過測試。

#include <iostream>
#include <cstring>  // for memset
#include <cmath>  // for abs
using namespace std;

int main() {
    int H, W, N, r, c, t, x;
    cin >> H >> W >> N;  // 讀取 H, W, N
    int canvas[H][W];  // 表示畫布狀態的 H*W 的二維陣列
    memset(canvas, 0, sizeof(canvas[0][0])*H*W);  // 將 canvas 內容初始化為0
    for(int i=0; i<N; i++) {  // 執行N次
        cin >> r >> c >> t >> x;  // 讀取 r, c, t, x
        int nri = (r-t > 0) ? (r-t) : 0, nrf = (r+t+1 < H) ? (r+t+1) : H;
        int nci = (c-t > 0) ? (c-t) : 0, ncf = (c+t+1 < W) ? (c+t+1) : W;
        for(int nr=nri; nr < nrf; nr++) {  // nr 的範圍為 0 或 (r-t) ~ (H-1) 或 (r+t)
            for(int nc=nci; nc < ncf; nc++) {  // nc 的範圍為 0 或 (c-t) ~ (W-1) 或 (c+t)
                if (abs(nr-r) + abs(nc-c) <= t)  // 如果 (nr, nc) 與 (r, c) 的曼哈頓距離小於等於 t
                   canvas[nr][nc] += x;  // 更新畫布 (nr, nc) 的值
            }
        }
    }
    // 印出答案
    for(int i=0; i<H; i++)
        for(int j=0; j<W; j++)
            cout << canvas[i][j] << " \n"[j == W-1];
    
    return 0;
}

<br /><br />

### 寫法2，使用 vector 及 algorithm

費時最久約為 3 ms，使用記憶體最多約為 332 kB，通過測試。

#include <iostream>
#include <cmath>  // for abs
#include <vector>
#include <algorithm>  // for max, min
using namespace std;

int main() {
    int H, W, N, r, c, t, x;
    cin >> H >> W >> N;  // 讀取 H, W, N
    vector<vector<int>> canvas (H, vector<int> (W, 0));  // 表示畫布狀態的 H*W 的二維陣列
    for(int i=0; i<N; i++) {  // 執行N次
        cin >> r >> c >> t >> x;  // 讀取 r, c, t, x
        for(int nr=max(0, r-t); nr < min(H, r+t+1); nr++) {  // nr 的範圍為 0 或 (r-t) ~ (H-1) 或 (r+t)
            for(int nc=max(0, c-t); nc < min(W, c+t+1); nc++) {  // nc 的範圍為 0 或 (c-t) ~ (W-1) 或 (c+t)
                if (abs(nr-r) + abs(nc-c) <= t)  // 如果 (nr, nc) 與 (r, c) 的曼哈頓距離小於等於 t
                   canvas[nr][nc] += x;  // 更新畫布 (nr, nc) 的值
            }
        }
    }
    // 印出答案
    for(int i=0; i<H; i++)
        for(int j=0; j<W; j++)
            cout << canvas[i][j] << " \n"[j == W-1];
    
    return 0;
}

<br /><br />

---

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