Digital Canvas (APCS 2024-06 Intermediate)

Points 100 1.0s 256M

There is a digital canvas with \(H\) rows and \(W\) columns. Every cell initially contains \(0\), meaning that no color has been added to it.

You will perform \(N\) brush operations. In one operation, the brush stays at coordinate \((r,c)\) for \(t\) seconds and adds color value \(x\) to every cell whose Manhattan distance from \((r,c)\) is at most \(t\). In other words, cell \((i,j)\) is affected when

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

If several operations affect the same cell, all their color values are added together. Output the canvas after all operations.

Input

The first line contains three positive integers \(H,W,N\): the number of rows, the number of columns, and the number of brush operations.

Each of the next \(N\) lines contains four integers \(r,c,t,x\), describing one operation. Rows and columns are both indexed from \(0\).

Constraints

  • \(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\)

Output

Print \(H\) lines, each containing \(W\) space-separated integers representing the canvas after all operations.

Scoring

The time limit for each test case is \(1\) second; your score is the sum over the test cases you pass. The subtasks are:

Subtask Points Additional constraint
1 60 \(H=1\)
2 40 No additional constraints

Sample Input 1

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

Sample Output 1

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

Sample Input 2

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

Sample Output 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

Source

Adapted from Problem 2, "Digital Canvas," of the June 2024 APCS programming test (ZeroJudge o077). The statement preparation also referred to Yizhe Wang's HackMD solution note.

Problem page help

Keyboard shortcuts

Main features

  • Sample tests — Runs the sample cases bundled with the problem and auto-compares against the expected output.
  • Custom test — Run your code with your own stdin. Optionally tick the "Compare with expected (diff)" box to verify against expected output line-by-line.
  • Template — Paste the default code template you set on your profile page.
  • Collab — Edit this problem together with classmates in real time.
  • Auto-draft — Editor contents auto-save to your browser every 1.5 seconds (per account / problem / language).
  • Submit — Send your code to the judge for grading; returns AC / WA / TLE etc.

Limits

  • Source code: at most 65,536 characters
  • Custom test stdin and expected output: at most 1 MB each (≈1 million characters)
  • Custom test and sample test share the sandbox; about 1 request per 3 s per user (sample test: 1 per 1 s)
  • Custom test and sample test both have a 15 second wall-clock cap (the official judge still uses the problem time limit)
  • Interactive problems do not offer custom test (cannot simulate interaction with the judge).
  • Submitting has no rate limit, but rapid repeated submissions on the same problem are treated as score farming.