[工程师死绝的世界A1001]有名なプールサイド 翻译
著名的水边
Translation by KSkun
原题:問題「有名なプールサイド」 | エンジニアが死滅シタ世界 〜アンドロイドとふたりぼっちで生きろ〜
问题描述
这次你负责设计一个新的城镇。
这个城镇的南北长 H ,东西宽 W ,一共由 H × W 个区域构成。
此外,所有的区域都被分配了一个坐标,如下图所示。
给定一个计划在城镇中建造的建筑物的列表。
每一座建筑物覆盖的区域都是矩形的,且只有一个门。
由于列表中包含了很多建筑物,可能无法建造出列表中所有的建筑物。
所以,你需要决定在城镇中建造哪些建筑物。
在决定建造哪些建筑物的时候,需要遵循以下 3 条规则。
- 建造的建筑物中,任意 2 座不能重叠。
- 建筑物的方向必须是表中给定的方向(建筑物不可旋转)。
- 可以通过“没有建筑物的区域”在任意 2 座建筑物的门之间移动。
这 3 条规则的形式化描述如下:
对于任意的 2 座建筑物,设它们的门的坐标分别为 P, Q 。
存在满足以下条件 (i)-(iii) 的一组坐标 (r_1, c_1), (r_2, c_2), …, (r_m, c_m) (m 是正整数) 。
- (i) 满足 1 ≦ r_i ≦ H, 1 ≦ c_i ≦ W (1 ≦ i ≦ m) 。
- (ii) 在坐标 (r_i, c_i) 处没有建造建筑物。
- (iii) 假设 P = (r_0, c_0), Q = (r_{m+1}, c_{m+1}) ,坐标 (r_i, c_i) 与 (r_{i+1}, c_{i+1}) 是相邻的坐标(即代表的区域共有上下左右边界之一) (0 ≦ i ≦ m) 。
下面的图片中展示了遵循条件 (i)-(iii) 的例子与不遵循它们的例子。
对于灰色与绿色建筑,你可以通过“没有建筑物的区域”在它们的门之间移动。
另一方面,对于灰色和蓝色建筑,不存在这样的移动方式。
一个覆盖了 X 个区域的建筑物会产生 X 万日元的利润。
请你编写一个程序,来计算使产生利润之和最大的建造建筑物的方案。
至少建造 1 座能产生利润的建筑物就判定为正确答案,得分根据产生利润之和的数值计算。
输入格式
H W N
h_1 w_1 r_1 c_1
h_2 w_2 r_2 c_2
...
h_N w_N r_N c_N
- 第一行包含三个整数,分别是表示城镇区域大小的 H, W 与表示建筑物列表中建筑物的数量 N ,数值之间用一个半角空格隔开。
- 接下来的 N 行中,第 i (1 ≦ i ≦ N) 行包含表示列表中第 i 座建筑物的信息的 4 个整数 h_i, w_i, r_i, c_i ,依次用一个半角空格隔开。
- h_i, w_i 分别表示第 i 座建筑物的南北长度与东西宽度。
- r_i, c_i 表示第 i 座建筑物的门的相对位置。门的位置为相对建筑物来说坐标 (r_i, c_i) 代表的区域,如下图所示。门在建筑物的外侧,且保证不在建筑物的四角上。
- 输入数据总共 N + 1 行,在最后一行之后有一个空行。
输出格式
请按以下格式输出建筑物的建造方案。
a_{1,1} a_{1,2} ... a_{1,W}
a_{2,1} a_{2,2} ... a_{2,W}
...
a_{H,1} a_{H,2} ... a_{H,W}
- 输出应当包含 H 行。
- 第 i (1 ≦ i ≦ H) 行中包含 W 个整数 a_{i,1}, a_{i,2}, …, a_{i,W} ,数字间用一个半角空格隔开。
- a_{i,j} 代表在坐标 (i, j) 处建造的建筑物的编号,如果此处没有建筑物则该值为 0 。此处建筑物的编号指建筑物列表中的建筑按照输入顺序的 1 到 N 的编号。
- 在输出的最后应包含一个空行,除此之外不应包含任何其他的字符或空行。
条件
- 2 ≦ H, W ≦ 100
- 1 ≦ N ≦ 100
- 对于任意的 1 ≦ i ≦ N
- 2 ≦ h_i ≦ H
- 2 ≦ w_i ≦ W
- 1 ≦ r_i ≦ h_i
- 1 ≦ c_i ≦ w_i
- 坐标 (r_i, c_i) 在建筑物的外侧(即至少满足 r_i = 1 、 r_i = h_i 、 c_i = 1 、 c_i = w_i 之中的一个条件)
- 坐标 (r_i, c_i) 不在建筑物的四角(即 (r_i, c_i) 不可能是 (1, 1), (1, w_i), (h_i, 1), (h_i, w_i) 中的任意一个)
- 保证能够建造的建筑物至少有 1 座。
输入输出样例
输入输出样例1
输入:
5 5 2
2 5 2 2
2 5 1 3
输出:
1 1 1 1 1
1 1 1 1 1
0 0 0 0 0
2 2 2 2 2
2 2 2 2 2
输入输出样例2
输入:
5 7 4
3 5 1 3
3 5 3 3
3 5 2 1
3 5 2 5
输出:
0 0 0 0 0 0 0
0 1 1 1 1 1 0
0 1 1 1 1 1 0
0 1 1 1 1 1 0
0 0 0 0 0 0 0
题解
本题没能找到什么思路……
求会写的dalao带带我QAQ