CF2271G Grid Filling

给定一个 $n \times m$ 的网格。行从上到下编号为 $1$ 到 $n$，列从左到右编号为 $1$ 到 $m$。如果两个格子有公共边，则认为它们相邻。 在该网格中有 $h$ 条水平切割线和 $v$ 条竖直切割线。第 $i$ 条水平切割线在第 $r_i$ 行和第 $r_i+1$ 行之间，且第 $j$ 条竖直切割线在第 $c_j$ 列和第 $c_j+1$ 列之间；每一条切割线都横跨整个网格。结合网格的边界，这些切割线将网格分割成 $(h + 1) \times (v + 1)$ 个矩形区域。 请使用正整数填写网格中的每一个格子，并满足以下两个条件： - 任何两个相邻的格子中填写的整数必须不同，即使它们属于不同的区域； - 每个由 $x$ 个格子组成的区域，必须恰好包含整数 $1,2,\ldots,x$ 各一次。 请找出一种满足上述条件的填充方案，或者判断是否不存在这样的填充方式。

输入包含多组测试数据。第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例的组数。 每个测试用例的第一行包含四个整数 $n$、$m$、$h$ 和 $v$（$1 \le n, m \le 1000$，$0 \le h < n$，$0 \le v < m$）——网格的行数、列数、水平切割线条数和竖直切割线条数。 接下来一行包含 $h$ 个整数 $r_1, r_2, \dots, r_h$（$1 \le r_1 < r_2 < \dots < r_h < n$），表示水平切割线的位置。如果 $h = 0$，则本行省略。 接下来一行包含 $v$ 个整数 $c_1, c_2, \dots, c_v$（$1 \le c_1 < c_2 < \dots < c_v < m$），表示竖直切割线的位置。如果 $v = 0$，则本行省略。 保证所有测试用例中 $n$ 的总和不超过 $1000$，$m$ 的总和也不超过 $1000$。

对于每个测试用例，如果不存在合法方案，输出 $-1$。 否则，输出 $n$ 行，每行 $m$ 个整数，表示从左到右填写在网格第 $i$ 行上的数值。 如果有多组合法解，输出任意一组均可。

在第一个样例中，一种可行的填充方式如图所示：  在第三个样例中，虚线为切割线。一种可行的填充方式如图所示：  在第四个样例中，可以证明不存在合法的填充方案。 由 ChatGPT 5 翻译