Problem A
Plotting the Pilt
With tensions easing between Piltover and Zaun, engineers from both cities have come together to build a new bridge across the River Pilt to signify a new, united beginning. However, to ensure the bridge’s foundation is stable, they first need a detailed topographical map of the riverbed. Using sonar, they’ve gathered depth measurements, but the raw data is difficult to interpret. Your task is to generate a clear visualization of the river floor.
You are given an $R \times
C$ grid of integers, $A$, where for $0 \leq i < R$ and $0 \leq j < C$, $A_{i, j}$ represents the depth
measurement at that location. Given a constant $d$, define $k_{i, j}$ as the largest value such
that $k_{i, j} \times d \leq
A_{i, j}$.
To represent the depth variations in a readable format, let
$m_{i, j}$ be the smallest
$k$ value among the
squares which share an edge with $(i,j)$, namely $(i \pm 1, j)$ and $(i, j \pm 1)$. Then, we can represent
location $(i,j)$ with:
-
‘ ’ (a space) if $k_{i, j}$ is less than or equal to $m_{i,j}$.
-
+ if $k_{i, j}$ is equal to $m_{i,j} + 1$.
-
X if $k_{i, j}$ is equal to $m_{i,j} + 2$.
-
# if $k_{i, j}$ is three or more greater than $m_{i,j}$.
Input
The first line contains three space-separated integers $R$, $C$, and $d \: (1 \leq R, C, d \leq 1\, 000, R \times C \geq 2)$, where $R$ and $C$ are the dimensions of the map and $d$ is the contour-scaling constant. After the first line, $R$ lines of input follow, where each line of input contains $C$ space-separated integers. When considering the $i$-th line after the first line, the $j$-th integer on this line will represent the depth measurement at that location $A_{i, j} \: (0 \leq A_{i,j} \leq 10\, 000)$.
Output
Output an $R \times C$ grid of characters, one character corresponding to each square.
| Sample Input 1 | Sample Output 1 |
|---|---|
1 4 100 0 100 300 600 |
+X# |
| Sample Input 2 | Sample Output 2 |
|---|---|
15 35 2 0 1 1 0 0 0 0 0 1 1 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 0 1 2 2 1 0 0 0 1 2 2 1 0 0 2 2 2 2 2 2 2 2 2 1 0 0 2 2 2 2 2 2 2 2 2 1 1 2 2 1 0 0 0 1 2 2 1 0 0 2 2 2 2 2 2 2 2 2 2 0 0 2 2 2 2 2 2 2 2 2 1 1 2 2 1 0 0 0 1 2 2 1 0 0 2 2 2 1 1 1 1 1 2 2 0 0 1 1 1 2 2 2 1 1 1 1 1 2 2 1 0 0 0 1 2 2 1 0 0 2 2 1 0 0 0 0 1 2 2 0 0 0 0 0 1 2 2 0 0 0 0 1 2 2 1 1 1 1 1 2 2 1 0 0 2 2 1 0 0 0 0 1 2 2 0 0 0 0 0 1 2 2 0 0 0 0 1 2 2 2 2 2 2 2 2 2 1 0 0 2 2 1 0 0 0 0 1 2 2 0 0 0 0 0 1 2 2 0 0 0 0 1 2 2 2 2 2 2 2 2 2 1 0 0 2 2 2 2 2 2 2 2 2 2 0 0 0 0 0 1 2 2 0 0 0 0 1 2 2 1 1 1 1 1 2 2 1 0 0 2 2 2 2 2 2 2 2 2 1 0 0 0 0 0 1 2 2 0 0 0 0 1 2 2 1 0 0 0 1 2 2 1 0 0 2 2 2 1 1 1 2 2 1 0 0 0 0 0 0 1 2 2 0 0 0 0 1 2 2 1 0 0 0 1 2 2 1 0 0 2 2 1 0 0 1 2 2 2 0 0 0 0 0 0 1 2 2 0 0 0 0 1 2 2 1 0 0 0 1 2 2 1 0 0 2 2 1 0 0 0 1 2 2 1 0 0 0 0 0 1 2 2 0 0 0 0 1 2 2 1 0 0 0 1 2 2 1 0 0 2 2 1 0 0 0 0 2 2 2 1 0 0 0 0 1 2 2 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 1 1 1 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 |
++ ++ +++++++++ +++++++++
++ ++ + +++++ + +++ +++
++ ++ + + ++ + +
++ ++ ++ ++ ++
++ ++ ++ ++ ++
+ +++++ + ++ ++ ++
+ +++++ + + ++++++ + ++
++ ++ + +++ + ++
++ ++ + + ++ ++
++ ++ ++ + + ++
++ ++ ++ ++ ++
++ ++ ++ +++ ++
|
| Sample Input 3 | Sample Output 3 |
|---|---|
15 15 43 86 138 178 234 289 329 341 341 325 309 265 210 154 99 66 120 175 222 288 354 399 416 420 406 388 343 281 218 152 117 146 204 256 330 404 453 475 481 469 450 404 336 268 194 156 186 246 302 385 469 521 549 558 546 524 478 404 330 246 208 218 277 336 425 515 570 604 617 608 586 543 466 388 299 260 242 302 364 459 555 614 654 666 657 635 595 515 435 339 302 265 322 385 484 583 645 691 703 694 672 638 558 478 379 343 277 329 391 490 589 651 700 712 703 682 654 577 500 401 368 269 315 376 472 567 626 675 688 682 663 641 570 500 404 375 261 302 361 453 546 601 651 663 660 645 629 564 500 407 381 234 267 320 404 487 537 583 592 589 577 567 512 456 373 354 194 218 265 336 407 450 493 503 503 496 496 453 410 339 326 154 173 216 277 339 379 419 429 432 432 438 404 370 308 298 123 138 175 228 280 314 348 354 354 354 361 333 305 253 246 111 125 159 208 256 288 319 326 326 326 333 309 284 236 230 |
+++++ +X+++ X++XXXXXX+XX++ +++XX+XX++X+X++ ++X+XX++XXXXX++ +++XXXXXX+X+#+X X+XXX++++X+#++ +++#XX++++X+#+ +XXXX+ + XXX++ ++X#+++ ++XX+ +++XX+XXXX+XX+ +++XXXXXXXX+X++ ++++XXXX++++X + ++++++++XXXX+X+ ++++++++++ X +++++ ++ |
