#4089
Entertaining Geodetics
Entertaining Geodetics
题目描述
在此游戏中地图被分为了许多叫作Geo格的正方形方格,其中一些被涂上色,假设没 有涂色的为透明色。 地图中还有些Geo符号,它们样子像不同颜色的金字塔(包括透明Geo符号)。每个 Geo符号都坐落在Geo格上,每个Geo格上最多一个Geo符号。 Geo符号可以被消除。为了更好地理解Geo符号在消除时发生了什么,这里引入把刚 消除的Geo符号放入的队列。 从队列中取出Geo符号,观察包含Geo符号的Geo格的颜色,如果它不是透明的且颜色 不同于Geo符号,则把所有这个颜色的Geo格重新涂为Geo符号的颜色(透明的Geo符号则 为透明色)。重涂色是在一个无限大的区域从那个有符号的Geo格子开始螺旋状进行的。 换句话说,我们选择所有需要重涂色的方格找到它们在以有符号格为中心的无限螺 旋表格中所对应的数字。此后按数字的增加顺序我们对其重染色。螺旋从中心格开始,先向上一步,然后按右、下、左、上的顺时针方向扩展;每走完两个方向,步长增加 1。中心编号为 1,中心附近的编号如下(行从上到下,列从左到右):
25 10 11 12 13
24 9 2 3 14
23 8 1 4 15
22 7 6 5 16
21 20 19 18 17
不因地图边界改变螺旋:只对地图内需要重涂色的格子按上述编号顺序处理。符号入队后仍记住原位置,出队时查询该位置当前的格子颜色;符号本身的颜色保持不变。一轮重涂色全部完成后,才处理下一个符号。这里的次数是所有轮次中重新涂色的格子数之和,同一格多次重新涂色要分别计数。
如果在重染色时遇到一个格子包含另一个Geo符号的情况则将Geo符号移出并放置在 队列尾部。 当重染色结束后Geo符号彻底消失,并且队列中下一个Geo符号(如果有)将取出, 重复此操作直至队列为空。 你知道所有格子的颜色、所有符号的位置。计算出队列里符号彻底消失时所造成的 重染色次数。 注意:答案可能超出 32 位整数范围,请使用 64 位整数类型。输入格式
第一行包含两个数n,m(1<=n,m<=300)—地图的高和宽。 接下来n行每行m个数—格子的颜色。 接下来n行每行m个数—对符号的描述,-1 表示没有符号,否则数字代表符号的颜色。 所有颜色都是属于0到10^9的整数,0表示透明。 最后一行两个数x,y(1<=x<=n,1<=y<=m)—需要消除的Geo符号的行和列位置。行从 上到下标记,列从左往右标记,从1开始。保证位置(x,y)包含一个符号。输出格式
一行一个数—符号消除时重染色次数。样例
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
35