← 返回题目列表

Codeforces · 15/D

D. 地图

中文机器翻译题面 查看原题

有一个区域地图,它是一个 n × m 的矩形矩阵,矩阵的每个单元格包含相应区域部分的平均高度。 Peter 工作的一家公司必须在该区域内建造多个城市,每个城市将占据地图上的一个 a × b 矩形单元格。为了在一个特定的地方开始建筑工程,彼得需要从将要建造新城市的建筑工地移除多余的土地。为此,他选择了该场地内的一个最小高度的单元,并从该场地的其他单元中移除了多余的地面,直至达到该最低水平。让我们考虑一下,要将地面水平从 h2 降低到 h1 (h1 ≤ h2),他们需要删除 h2 - h1 地面单位。

如果与其他可能的位置相比,从该站点移除的地面量最少,我们称该站点的位置为最佳。彼得根据以下算法构建城市:从所有最佳地点的位置中,他选择最上面的一个。如果这个位置不是唯一的,他会选择最左边的位置。然后他在这个地方建造了一座城市。彼得重复这个过程,直到他能再建造至少一座城市。当然,他不能在被占用的牢房上进行建筑工程。请你帮彼得根据算法放置城市好吗?

输入

第一行包含四个空格分隔的整数:地图大小 n、m 和城市大小 a、b (1 ≤ a ≤ n ≤ 1000, 1 ≤ b ≤ m ≤ 1000)。接下来是 n 行,每行包含 m 个非负空格分隔的数字,描述高度矩阵。每个数字不超过109。

输出

第一行输出k——已建城市数量。在接下来的 k 行中,每一行输出 3 个空格分隔的数字——后续施工场地左上角的行号和列号,以及要从中移除的地面量。按照站点建立的顺序输出站点。

示例

输入 #1

2 2 1 2
1 2
3 5

输出 #1

2
1 1 1
2 1 2

输入 #2

4 4 2 2
1 5 3 4
2 7 6 1
1 1 2 2
2 2 1 2

输出 #2

3
3 1 2
3 3 3
1 2 9