QOJ.ac

QOJ

実行時間制限: 3 s メモリ制限: 1024 MB 満点: 100

#4069. 清空波罗的海

統計

Gunnar 不喜欢自然力量,总是想出一些创新的计划来减少它们对自己的影响。尽管他之前在斯德哥尔摩上空建造巨型穹顶以抵御过强阳光(以及雨雪)的计划尚未实现,但他现在正专注于通过一个优雅的方案——直接将波罗的海从等式中移除——来预先应对气候变化可能对波罗的海产生的影响。

Picture by Jeremy Halls on Flickr, cc by-sa

首先,Gunnar 想要建造一道连接丹麦和挪威的防洪堤,将波罗的海与大西洋隔开。这道防洪堤还将有助于保护北欧国家免受海平面上升的影响。接下来,Gunnar 安装了一个可以从海底排干波罗的海水的装置。该装置会将所需的水量排干到地核,在那里水将永远消失(因为在 Gunnar 看来,物理学就是这样运作的)。然而,根据装置放置的位置,整个波罗的海可能无法被完全排干——可能会残留一些水洼。

为了简化问题,Gunnar 使用一个二维网格来近似表示波罗的海的地图,每个网格代表 1 米见方的区域。对于网格上的每个方格,他计算了平均海拔。海拔为负的方格被水覆盖,海拔非负的方格则是干燥的。海拔以海平面以上的米数给出,因此海平面的海拔恰好为 0。他忽略了海平面以下的湖泊和干地,因为无论如何,这些都不会对估算产生太大影响。

网格上一个方格中的水可以流向其 8 个邻居中的任何一个,即使两个方格仅共享一个角。地图被干地包围,因此水永远不会流出地图之外。水遵循重力规律,因此它只能流向更靠近地核的地方——要么通过排水装置,要么流向水位较低的相邻方格。

Gunnar 更像是一个有想法的人,而不是程序员,所以他请求你帮助评估在给定装置放置位置的情况下,会有多少水被排干。

输入格式

第一行包含两个整数 $h$ 和 $w$,$1 \le h, w \le 500$,表示地图的高度和宽度。

接下来是 $h$ 行,每行包含 $w$ 个整数。第一行代表 Gunnar 地图的最北端。每个整数代表地图网格上一个方格的海拔。海拔以米为单位,且至少为 $-10^6$,至多为 $10^6$。

最后一行包含两个整数 $i$ 和 $j$,$1 \le i \le h, 1 \le j \le w$,表示排水装置放置在第 $i$ 行第 $j$ 列对应的单元格中。你可以假设位置 $(i, j)$ 的海拔为负(即排水装置没有放置在陆地上)。

输出格式

输出一行,包含一个整数——排干的海水总体积,单位为立方米。

样例

输入格式 1

3 3
-5 2 -5
-1 -2 -1
5 4 -5
2 2

输出格式 1

10

输入格式 2

2 3
-2 -3 -4
-3 -2 -3
2 1

输出格式 2

16

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.