CF2271G.Grid Filling
NOI/NOI+/CTSC
通过率:0%
时间限制:2.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
You are given a grid of size n×m. The rows are numbered from 1 to n from top to bottom, and the columns are numbered from 1 to m from left to right. Two cells are adjacent if they share a side.
There are h horizontal and v vertical cuts in the grid. The i-th horizontal cut goes between rows ri and ri+1, and the j-th vertical cut goes between columns cj and cj+1; every cut crosses the whole grid. Together with the borders of the grid, the cuts split it into (h+1)⋅(v+1) rectangular pieces.
Write a positive integer in every cell of the grid so that both of the following conditions hold:
- any two adjacent cells contain different integers, even if these cells belong to different pieces;
- every piece consisting of x cells contains each of the integers 1,2,…,x exactly once.
Find any way to fill the grid satisfying these conditions, or determine that it is impossible.
你被给定一个大小为 n×m 的网格。行从上到下编号为 1 到 n,列从左到右编号为 1 到 m。若两个格子共享一条边,则称它们相邻。
网格中有 h 条水平切割线和 v 条垂直切割线。第 i 条水平切割线位于第 ri 行与第 ri+1 行之间,第 j 条垂直切割线位于第 cj 列与第 cj+1 列之间;每条切割线均横贯整个网格。这些切割线连同网格的边界一起,将网格划分为 (h+1)⋅(v+1) 个矩形区域。
请在网格的每个格子中填入一个正整数,使得以下两个条件同时成立:
- 任意两个相邻格子中的整数互不相同(即使这两个格子属于不同的区域);
- 每个由 x 个格子组成的区域,必须恰好包含整数 1,2,…,x 各一次。
请找出一种满足上述条件的填数方案,或判定该问题无解。
输入格式
Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤1000). The description of the test cases follows.
The first line of each test case contains four integers n, m, h, and v (1≤n,m≤1000, 0≤h<n, 0≤v<m) — the number of rows of the grid, the number of columns of the grid, the number of horizontal cuts, and the number of vertical cuts.
The next line contains h integers r1,r2,…,rh (1≤r1<r2<…<rh<n) — the positions of the horizontal cuts. If h=0, this line is not present.
The next line contains v integers c1,c2,…,cv (1≤c1<c2<…<cv<m) — the positions of the vertical cuts. If v=0, this line is not present.
It is guaranteed that the sum of n over all test cases does not exceed 1000.
It is guaranteed that the sum of m over all test cases does not exceed 1000.
每个测试包含多个测试用例。第一行包含测试用例的数量 t(1≤t≤1000)。随后是各测试用例的描述。
每个测试用例的第一行包含四个整数 n、m、h 和 v(1≤n,m≤1000,0≤h<n,0≤v<m)—— 分别表示网格的行数、列数、水平切割次数和垂直切割次数。
接下来的一行包含 h 个整数 r1,r2,…,rh(1≤r1<r2<…<rh<n)—— 表示水平切割的位置。若 h=0,则该行不存在。
再下一行包含 v 个整数 c1,c2,…,cv(1≤c1<c2<…<cv<m)—— 表示垂直切割的位置。若 v=0,则该行不存在。
保证所有测试用例中 n 的总和不超过 1000。
保证所有测试用例中 m 的总和不超过 1000。
输出格式
For each test case, if there is no valid way to fill the grid, output −1.
Otherwise, output n lines. The i-th of these lines should contain m integers — the numbers written in the cells of the i-th row of the grid, from left to right.
If there are multiple valid ways to fill the grid, output any of them.
对于每个测试用例,若不存在填充网格的有效方案,则输出 −1。
否则,输出 n 行。其中第 i 行应包含 m 个整数——即网格第 i 行中从左到右各单元格所填的数字。
若存在多种有效的填充方案,输出任意一种即可。
输入输出样例
输入#1
4 3 3 0 0 1 6 0 2 1 3 5 5 2 2 2 3 2 3 4 4 2 2 1 2 1 2
输出#1
1 2 3 4 5 6 7 8 9 1 2 1 2 1 3 1 2 1 2 1 3 4 2 3 4 1 2 1 2 1 3 4 2 3 4 1 2 1 2 1 -1
说明/提示
In the first example, one possible way to fill the grid is shown below:

In the third example, the dashed lines represent the cuts. One possible way to fill the grid is shown below:

In the fourth example, it can be shown that no valid filling exists.
在第一个例子中,一种可能的网格填充方式如下所示:

在第三个例子中,虚线表示切割线。一种可能的网格填充方式如下所示:

在第四个例子中,可以证明不存在合法的填充方案。
输入解题思路,AI测评打分。不知道怎么写?