5438 - Entertaining Geodetics
在此游戏中地图被分为了许多叫作Geo格的正方形方格,其中一些被涂上色,假设没有涂色的为透明色。
地图中还有些Geo符号,它们样子像不同颜色的金字塔(包括透明Geo符号)。每个Geo符号都坐落在Geo格上,每个Geo格上最多一个Geo符号。
Geo符号可以被消除。为了更好地理解Geo符号在消除时发生了什么,这里引入把刚消除的Geo符号放入的队列。
从队列中取出Geo符号,观察包含Geo符号的Geo格的颜色,如果它不是透明的且颜色不同于Geo符号,则把所有这个颜色的Geo格重新涂为Geo符号的颜色(透明的Geo符号则为透明色)。重涂色是在一个无限大的区域从那个有符号的Geo格子开始螺旋状进行的。
换句话说,我们选择所有需要重涂色的方格找到它们在以有符号格为中心的无限螺旋表格中所对应的数字。此后按数字的增加顺序我们对其重染色。
如果在重染色时遇到一个格子包含另一个Geo符号的情况则将Geo符号移出并放置在队列尾部。
当重染色结束后Geo符号彻底消失,并且队列中下一个Geo符号(如果有)将取出,重复此操作直至队列为空。
为了更好地理解请看一个例子。
你知道所有格子的颜色、所有符号的位置。计算出队列里符号彻底消失时所造成的重染色次数。
推荐使用I64d输出。
输入
第一行包含两个数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
来源
蓝桥杯