CF1416F Showing Off

又是一个无聊的隔离日，BThero 决定开始研究大小为 $n \times m$ 的矩阵。行从上到下编号为 $1$ 到 $n$，列从左到右编号为 $1$ 到 $m$。第 $i$ 行第 $j$ 列的单元格记作 $(i, j)$。 对于每个单元格 $(i, j)$，BThero 有两个值： 1. 该单元格的代价，是一个正整数。 2. 该单元格的方向，是字符 L、R、D、U 之一。这些字符分别表示向相邻的左 $(i, j-1)$、右 $(i, j+1)$、下 $(i+1, j)$ 或上 $(i-1, j)$ 的单元格转移。没有任何转移会指向矩阵外部。 我们称，如果从 $(i_1, j_1)$ 出发，按照当前单元格的方向不断移动到相邻单元格，最终能够访问到 $(i_2, j_2)$，则 $(i_2, j_2)$ 可从 $(i_1, j_1)$ 到达。 BThero 决定用已有的两个矩阵生成另一个矩阵。对于单元格 $(i, j)$，记 $S_{i, j}$ 为从该单元格出发能够到达的所有单元格的集合（包括 $(i, j)$ 本身）。那么，新矩阵中 $(i, j)$ 位置的值等于 $S_{i, j}$ 中所有单元格的代价之和。 BThero 很快计算出了新矩阵，并立即把它发给了朋友们。然而，他并没有保存最初的两个矩阵！请你帮他还原出任意一组合法的初始矩阵，使得它们能够生成当前的新矩阵。

输入文件的第一行包含一个整数 $T$（$1 \le T \le 100$），表示测试用例的数量。接下来是 $T$ 个测试用例的描述。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n \cdot m \le 10^5$）。 接下来的 $n$ 行，每行包含 $m$ 个整数，表示生成的新矩阵的元素。每个元素属于区间 $[2, 10^9]$。 保证所有测试用例中 $\sum{(n \cdot m)} \le 10^5$。

对于每个测试用例，如果不存在答案，输出一行 NO。否则，输出 YES，并输出两个矩阵，格式与输入相同。 - 第一个矩阵为代价矩阵，第二个矩阵为方向矩阵。 - 代价矩阵中的所有整数均为正数。 - 方向矩阵中的所有字符均为有效方向，且不会指向矩阵外部。

由 ChatGPT 4.1 翻译