CF2055C The Trail

佛罗里达没有山脉，佛罗里达人无法理解它们的存在。因此，他非常需要你的帮助。 在荒野中有一片山区地带，用一个 $n$ 行 $m$ 列的矩形网格表示。网格中的每个单元格由其位置 $(i, j)$ 标识，其中 $i$ 是行索引，$j$ 是列索引。单元格 $(i, j)$ 的海拔高度记为 $a_{i,j}$。 然而，这片区域被人为篡改过。一条由 $n+m-1$ 个单元格组成的路径，从左上角 $(1, 1)$ 出发，最终到达右下角 $(n, m)$，路径上的每个单元格 $(i, j)$ 的高度 $a_{i,j}$ 都被设置为 $0$。这条路径只能严格地向下（$\mathtt{D}$）或向右（$\mathtt{R}$）移动。 为了恢复地形的原貌，已知在被篡改之前，这片区域拥有一种神奇的性质：所有行和所有列的海拔高度之和都相同。更正式地说，存在一个整数 $x$，使得对于所有 $1\le i\le n$，都有 $\sum_{j=1}^m a_{i, j} = x$，并且对于所有 $1\le j\le m$，都有 $\sum_{i=1}^n a_{i, j} = x$。 你的任务是为路径上的单元格重新赋予高度，使上述神奇性质得以恢复。可以证明，总是存在解。如果有多个满足条件的解，输出任意一个即可。

每个测试点包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$2 \leq n, m \leq 1000$），表示网格的行数和列数。 第二行包含一个长度为 $n+m-2$ 的字符串 $s$（$s_i = \mathtt{D}$ 或 $s_i = \mathtt{R}$），表示从 $(1, 1)$ 到 $(n, m)$ 的路径。字符 $\mathtt{D}$ 表示向下走一步，$\mathtt{R}$ 表示向右走一步。 接下来的 $n$ 行，每行包含 $m$ 个整数 $a_{i,1}, a_{i,2}, \ldots, a_{i,m}$（$-10^6 \leq a_{i,j} \leq 10^6$），表示网格中每个单元格的高度。保证如果单元格 $(i, j)$ 在路径上，则 $a_{i,j} = 0$。 保证所有测试用例中 $n \cdot m$ 的总和不超过 $10^6$。

对于每个测试用例，输出 $n$ 行，每行 $m$ 个整数，表示恢复后的网格高度 $b_{i, j}$。要求 $-10^{15} \leq b_{i,j} \leq 10^{15}$，并且如果 $(i, j)$ 不在路径上，则 $a_{i,j} = b_{i,j}$。如果有多个解，输出任意一个即可。

在第一个测试用例中，网格被填充为每行和每列都包含 $1, 2, 3$，它们的和都是 $6$。 在第二个测试用例中，网格被填充为所有行和列的和都是 $0$。 由 ChatGPT 4.1 翻译