← 返回题目列表

Codeforces · 105/D

D. 有趣的大地测量学

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

游戏中的地图分为称为地理面板的方形单元格。其中一些面板被涂漆。我们假设没有颜色的地理面板被涂成透明颜色。

此外,地图上还有所谓的地理符号。它们看起来像不同颜色的金字塔(包括透明颜色的地理符号)。每个地理符号位于一个地理面板上,并且每个地理面板最多可以包含一个地理符号。

地理符号可以被消除。为了更好地理解消除地理符号时会发生什么,让我们引入一些队列,将最近消除的地理符号放入其中。

让我们将刚刚被消除的地理符号放在队列的头部。接下来,我们将重复以下操作:

从队列中提取地理符号。查看包含给定地理符号的面板的颜色。如果它不同于透明且不同于地理符号的颜色,则该颜色的所有地理面板都将重新绘制为给定地理符号的颜色(透明地理符号会将地理面板重新绘制为透明)。从包含地理符号的面板开始,严格按照以下顺序以无限螺旋方式执行重新绘制:

换句话说,我们选择所有需要重新绘制的面板,并在其中心位于给定地理符号位置的无限螺旋中找到它们的编号。之后,我们按照数字递增的顺序重新绘制它们。

如果面板包含另一个地理符号并且正在重新绘制该面板,则该地理符号将从字段中删除并放置在队列的末尾。

重新绘制后,地理符号被完全消除,并且从队列的头部(如果有的话)取出下一个地理符号,并重复该过程。如果队列为空,则该过程结束。

请参阅示例分析以更好地理解。

您知道所有地理面板的颜色以及所有地理符号的位置。确定重画的次数,如果您破坏了其中一个地理符号,就会发生重画的次数。

输入

第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 300) — 地图的高度和宽度(以单元格为单位)。

然后跟随n行;每个都包含 m 个数字——地理面板的颜色。

然后再执行 n 行;每个都包含 m 个数字——地理符号的描述。 -1 表示给定位置不包含地理符号。否则,该数字表示给定位置的地理符号的颜色。

所有颜色均为 0 到 109 之间的整数。0 表示透明颜色。

最后一行包含两个整数x和y(1≤x≤n,1≤y≤m)——需要消除的地理符号所在的行和列。行从上到下编号,列从左到右编号。坐标从 1 开始。保证坐标为(x,y)的位置包含地理符号。

输出

打印单个数字——消除地理符号后重新绘制的总数。

请不要使用 %lld 说明符在 C++ 中读取或写入 64 位整数。最好使用 cout 流(您也可以使用 %I64d 说明符)。

示例

输入 #1

5 5
9 0 1 1 0
0 0 3 2 0
1 1 1 3 0
1 1 1 3 0
0 1 2 0 3
-1 1 -1 3 -1
-1 -1 -1 0 -1
-1 -1 -1 -1 -1
-1 2 3 -1 -1
-1 -1 -1 -1 2
4 2

输出 #1

35

注意

示例的所有操作可以在下图中看到:

http://assets.codeforces.com/images/geo_slow.gif