2055C.md (3486B)
1 Source: https://codeforces.com/problemset/problem/2055/C 2 3 C. The Trail 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 | | 22 | --- | 23 | There are no mountains in Florida, and Florida Man cannot comprehend their existence. As such, he really needs your help with this one. | 24 25 In the wilderness lies a region of mountainous terrain represented as a rectangular grid with $n$ rows and $m$ columns. Each cell in the grid is identified by its position $(i, j)$, where $i$ is the row index and $j$ is the column index. The altitude of cell $(i, j)$ is denoted by $a_{i,j}$. 26 27 However, this region has been tampered with. A path consisting of $n + m - 1$ cells, starting from the top-left corner $(1, 1)$ and ending at the bottom-right corner $(n, m)$, has been cleared. For every cell $(i, j)$ along this path, the altitude $a_{i,j}$ has been set to $0$. The path moves strictly via downward ($\mathtt{D}$) or rightward ($\mathtt{R}$) steps. 28 29 To restore the terrain to its original state, it is known that the region possessed a magical property before it was tampered with: all rows and all columns shared the same sum of altitudes. More formally, there exists an integer $x$ such that $\sum_{j=1}^m a_{i, j} = x$ for all $1\le i\le n$, and $\sum_{i=1}^n a_{i, j} = x$ for all $1\le j\le m$. 30 31 Your task is to assign new altitudes to the cells on the path such that the above magical property is restored. It can be proven that a solution always exists. If there are multiple solutions that satisfy the property, any one of them may be provided. 32 33 Input 34 35 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows. 36 37 The first line of each test case contains two integers $n$ and $m$ ($2 \leq n, m \leq 1000$) — the number of rows and columns in the grid. 38 39 The second line of each test case contains a string $s$ of length $n+m-2$ ($s_i = \mathtt{D}$ or $s_i = \mathtt{R}$) — the steps the path makes from $(1, 1)$ to $(n, m)$. The character $\mathtt{D}$ represents a downward step, and $\mathtt{R}$ represents a rightward step. 40 41 The $i$-th of the next $n$ lines each contain $m$ integers $a_{i,1}, a_{i, 2}, \ldots, a_{i,m}$ ($-10^6 \leq a_{i,j} \leq 10^6$) — the altitude of each cell in the grid. It is guaranteed that if a cell $(i, j)$ lies on the path, then $a_{i,j} = 0$. 42 43 It is guaranteed that the sum of $n \cdot m$ over all test cases does not exceed $10^6$. 44 45 Output 46 47 For each test case, output $n$ lines of $m$ integers representing the restored grid of altitudes $b_{i, j}$. The altitudes must satisfy $-10^{15} \leq b_{i,j} \leq 10^{15}$, and additionally $a_{i,j} = b_{i,j}$ if $(i, j)$ is not on the path. If multiple solutions exist, output any of them. 48 49 Example 50 51 Input 52 53 ``` 54 4 55 56 3 3 57 58 DRRD 59 60 0 2 3 61 62 0 0 0 63 64 3 1 0 65 66 4 5 67 68 DRRRRDD 69 70 0 1 0 2 3 71 72 0 0 0 0 0 73 74 -1 0 -3 -3 0 75 76 0 0 0 -1 0 77 78 2 3 79 80 RRD 81 82 0 0 0 83 84 0 1 0 85 86 5 5 87 88 DDDDRRRR 89 90 0 25 2 9 11 91 92 0 6 13 20 22 93 94 0 17 24 1 8 95 96 0 3 10 12 19 97 98 0 0 0 0 0 99 ``` 100 101 Output 102 103 ``` 104 1 2 3 105 2 3 1 106 3 1 2 107 -6 1 0 2 3 108 7 -1 3 2 -11 109 -1 0 -3 -3 7 110 0 0 0 -1 1 111 0 -1 1 112 0 1 -1 113 18 25 2 9 11 114 4 6 13 20 22 115 15 17 24 1 8 116 21 3 10 12 19 117 7 14 16 23 5 118 ``` 119 120 Note 121 122 In the first test case, the grid has been filled such that every row and column contains the numbers $1, 2, 3$ in some order, resulting in a common sum of $6$. 123 124 In the second test case, the grid has been filled such that all rows and columns sum to $0$.