題解

電子畫布 (APCS 2024-06 中級)

1.0s 256M

有一張由 \(H\) 列、\(W\) 欄組成的電子畫布。畫布上的每一格起初都是 \(0\)，表示尚未填入任何顏色。

接下來會進行 \(N\) 次畫筆操作。一次操作會讓畫筆停在座標 \((r,c)\) \(t\) 秒，並把所有與 \((r,c)\) 的曼哈頓距離不超過 \(t\) 的格子加上顏色值 \(x\)。也就是說，格子 \((i,j)\) 會在

\[|i-r|+|j-c|\le t\]

時受到這次操作影響。

如果同一格受到多次操作，所有顏色值都要累加。請輸出完成全部操作後的 畫布。

輸入格式

第一行包含三個正整數 \(H,W,N\)，依序表示畫布的列數、欄數與畫筆操作 次數。

接下來 \(N\) 行，每行包含四個整數 \(r,c,t,x\)，表示一次畫筆操作。 畫布的列與欄皆從 \(0\) 開始編號。

限制

  • \(1\le H,W\le20\)
  • \(1\le N\le100\)
  • \(0\le r<H\)
  • \(0\le c<W\)
  • \(0\le t\le20\)
  • \(1\le x\le10\)

輸出格式

輸出 \(H\) 行，每行包含 \(W\) 個以空白分隔的整數，表示完成全部操作後的 畫布。

評分說明

每一筆測試資料的執行時間限制均為 \(1\) 秒，依正確通過的測試資料筆數給分。其中：

子題 分數 額外限制
1 60 \(H=1\)
2 40 無額外限制

範例輸入 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

題目來源

改編自 APCS 2024 年 6 月實作題第 2 題「電子畫布」 （ZeroJudge o077）； 題意整理另參考王一哲的 HackMD 題解。

題目頁說明

快速鍵

主要功能

  • 範例測試 — 執行題目附帶的範例測資並自動比對預期輸出。
  • 自訂測試 — 自己貼 stdin 執行程式。可勾選「與預期輸出比對 (diff)」做行對行比對。
  • 模板 — 貼上你在個人資料設定的預設程式碼模板。
  • 協作 — 與其他同學共筆編輯這題的程式碼。
  • 自動草稿 — 編輯器內容每 1.5 秒自動存到瀏覽器（per 帳號 / 題目 / 語言）。
  • 提交 — 把程式碼交給 judge 評測，回傳 AC / WA / TLE 等結果。

限制

  • 程式碼最多 65,536 字元
  • 自訂測試 stdin 與預期輸出各最多 1 MB （約 100 萬字元）
  • 自訂測試與範例測試共用一個沙箱，每人約 3 秒 1 次 （範例測試 1 秒 1 次）
  • 自訂測試與範例測試都有 15 秒 牆鐘上限（正式評測仍依題目原本時限）
  • 互動題不提供自訂測試（無法模擬與 judge 互動）。
  • 提交評測本身沒有 rate limit，但同題短時間內多次提交會被視為刷分。