QOJ.ac

QOJ

実行時間制限: 1 s メモリ制限: 32 MB 満点: 100

#13074. 金字塔

統計

在赢得一场伟大的战役后,美洲豹国王(King Jaguar)想要建造一座金字塔,既作为纪念他胜利的丰碑,也作为在战斗中牺牲的勇敢士兵的陵墓。金字塔将建在战场上,其底座为 $a$ 列 $b$ 行的矩形。在金字塔内部的地面层,有一个 $c$ 列 $d$ 行的较小矩形墓室,用于安放阵亡士兵的遗体和武器。

国王的建筑师们将战场勘测为一个 $m$ 列 $n$ 行的网格,并测量了每个方格的海拔高度(整数)。

金字塔和墓室都必须覆盖网格中的完整方格,且其边必须与战场的边平行。墓室所在方格的海拔高度必须保持不变,但金字塔底座其余部分的地面将通过从较高方格向较低方格搬运沙土来平整。底座的最终海拔高度将是底座所有方格(不包括墓室所在方格)的平均海拔高度。建筑师可以自由地将内部墓室放置在金字塔内的任何位置,只要在墓室周围留出至少一格宽的墙壁即可。

请帮助建筑师选择放置金字塔和内部墓室的最佳位置,使得在给定尺寸下,底座的最终海拔高度尽可能高。

下图展示了一个战场示例;每个方格中的数字代表该位置地形的海拔高度。灰色方格代表金字塔的底座,被包围的白色方格代表墓室。该图展示了一种最优放置方案。

任务

编写一个程序,给定战场、金字塔和墓室的尺寸,以及战场上每个方格的海拔高度,确定金字塔在战场中的位置以及墓室在金字塔内的位置,使得底座的海拔高度尽可能高。

数据范围

$3 \le m \le 1000$ $3 \le n \le 1000$ $3 \le a \le m$ $3 \le b \le n$ $1 \le c \le a - 2$ $1 \le d \le b - 2$ 所有海拔高度均为 $1$ 到 $100$ 之间的整数。

输入格式

第一行包含六个空格分隔的整数,依次为:$m, n, a, b, c, d$。 接下来的 $n$ 行,每行包含 $m$ 个空格分隔的整数,表示网格中每一行的海拔高度。第一行表示网格的顶行(第 $1$ 行),最后一行表示底行(第 $n$ 行)。每行中的 $m$ 个整数表示从第 $1$ 列开始该行各方格的海拔高度。

输出格式

第一行:包含两个空格分隔的整数,表示金字塔底座的左上角坐标,第一个数字为列号,第二个数字为行号。 第二行:包含两个空格分隔的整数,表示金字塔内墓室的左上角坐标,第一个数字为列号,第二个数字为行号。

说明

如果存在多个最优放置方案,输出其中任何一个均被视为正确。

子任务

对于总分 $30$ 分的测试用例,每次测试运行将满足以下要求: $3 \le m \le 10$ $3 \le n \le 10$

样例

输入 1

8 5 5 3 2 1
1 5 10 3 7 1 2 5
6 12 4 4 3 3 1 5
2 4 3 1 6 6 19 8
1 1 1 3 4 2 4 5
6 6 3 3 3 2 2 2

输出 1

4 1
6 2

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.