DMOPC '21 Contest 6 P3 - An Art Problem

View as PDF

Submit solution


Points: 10 (partial)
Time limit: 3.0s
Memory limit: 1G

Author:
Problem type

Alice has just created an N \times M-pixel drawing on a digital art program. Each pixel can be coloured in one of 10^9 different colours, numbered from 1 to 10^9, or it can be blank, in which case it will be numbered with 0.

After Alice finished the drawing, she decided that it would look better if the edges of the drawing were expanded by K pixels, maintaining colour. More specifically, let a step be a move of one pixel directly up, down, left, or right. If a blank pixel is K or fewer steps away from a coloured pixel, it should take on the colour of that pixel. If multiple pixels are K or fewer steps away, choose the colour of the closest one, and if multiple pixels are equally close, choose the lowest-numbered colour among them.

Please help Alice do this!

Constraints

1 \le N, M, K \le 1\,500

0 \le c_{i, j} \le 10^9

Subtask 1 [2/15]

1 \le N, M, K \le 50

Subtask 2 [2/15]

1 \le N, M, K \le 400

0 \le c_{i, j} \le 1

Subtask 3 [3/15]

1 \le N, M, K \le 400

Subtask 4 [3/15]

0 \le c_{i, j} \le 1

Subtask 5 [5/15]

No additional constraints.

Input Specification

The first line contains three space-separated integers, N, M, and K.
The next N lines each contain M space-separated integers: the colour c_{i, j} of each pixel.

Output Specification

Output N lines, each containing M space-separated integers: the drawing after being expanded by K pixels.

Sample Input

3 10 1
0 0 0 0 0 0 0 0 0 0
0 0 1 1 1 2 2 2 0 0
0 0 0 0 0 0 0 0 0 0

Sample Output

0 0 1 1 1 2 2 2 0 0
0 1 1 1 1 2 2 2 2 0
0 0 1 1 1 2 2 2 0 0

Comments

There are no comments at the moment.