著名的水边

Translation by KSkun

原题：問題「有名なプールサイド」 | エンジニアが死滅シタ世界 〜アンドロイドとふたりぼっちで生きろ〜

问题描述

这次你负责设计一个新的城镇。
这个城镇的南北长 H ，东西宽 W ，一共由 H × W 个区域构成。
此外，所有的区域都被分配了一个坐标，如下图所示。

给定一个计划在城镇中建造的建筑物的列表。
每一座建筑物覆盖的区域都是矩形的，且只有一个门。

由于列表中包含了很多建筑物，可能无法建造出列表中所有的建筑物。
所以，你需要决定在城镇中建造哪些建筑物。

在决定建造哪些建筑物的时候，需要遵循以下 3 条规则。

1. 建造的建筑物中，任意 2 座不能重叠。
2. 建筑物的方向必须是表中给定的方向（建筑物不可旋转）。
3. 可以通过“没有建筑物的区域”在任意 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