3525. [USACO20Dec Gold]Replication

【题目描述】

在网上观看太多机械 DIY 视频的后果就是，Farmer John 偶然在他的农场上制造了一个可以自我复制的机器人！

农场可以用一个 $N\times N$ 的方阵表示（$3\le N\le 1000$），其中每个方格是空的或有岩石，并且所有边界上的方格均有岩石。某些没有岩石的方格被指定为机器人可能的起始位置。

Farmer John 初始将机器人放置在可能的起始位置之一。在之后的每一个小时，机器人的所有副本会沿着相同的方向移动一格，向北、向南、向东或向西。每 $D$ 个小时（$1 \leq D \leq 10^9$）之后，机器人的每个副本会进行自我复制——在方格 $(x,y)$ 进行自我复制的机器人会在方格 $(x+1,y)$、$(x-1,y)$、$(x,y+1)$ 以及 $(x,y-1)$ 产生机器人的新的副本；原本的机器人仍然位于 $(x,y)$。一段时间过后，同一方格内可能会有多个机器人。

如果移动或复制会使得任何一个机器人撞到岩石，那么所有的机器人均立刻停止行动。注意由于农场的边界都是岩石，这意味着所有机器人最终必然会停下。

请帮助奶牛们求出可能在某个时刻含有机器人的空的方格数量。

【输入格式】

输入的第一行包含两个空格分隔的整数 $N$ 和 $D$。以下 $N$ 行每行包含 $N$ 个字符。每个字符均为 '.'、'S' 和 '#' 之一。'.' 和 'S' 均表示空的方格，且 'S' 表示一个可能的机器人起始位置。'#' 表示一块岩石。

所有第一行、最后一行、第一列、最后一列的字符均为 '#'。

【输出格式】

输出一个整数，表示可能在某个时刻含有机器人的方格数量。

【样例输入1】

10 1
##########
#........#
#S.......#
#........#
##########
#S....S..#
##########
##########
##########
##########

【样例输出1】

15

【样例输入2】

10 2
##########
#.#......#
#.#......#
#S.......#
#.#......#
#.#......#
##########
##########
##########
##########

【样例输出2】

28

【样例输入3】

10 2
##########
#.S#.....#
#..#.....#
#S.......#
#..#.....#
#..#.....#
##########
##########
##########
##########

【样例输出3】

10

【样例说明】

【样例 1 解释】

在以下的图中，x 表示机器人。

可能含有机器人的位置为：

##########
#xxx.....#
#xxxx....#
#xxx.....#
##########
#xx..xxx.#
##########
##########
##########
##########

以下是一个可能的事件序列：

• FJ 将机器人放在了左上的起始位置。
• 机器人向右移动一个单位。
• 机器人进行自我复制。
• 所有机器人向右移动一个单位。
• 再一次自我复制会导致存在机器人撞到岩石，所以该过程终止。

##########    ##########    ##########    ##########
#........#    #........#    #.x......#    #..x.....#
#x.......#    #.x......#    #xxx.....#    #.xxx....#
#........#    #........#    #.x......#    #..x.....#
########## -> ########## -> ########## -> ##########
#........#    #........#    #........#    #........#
##########    ##########    ##########    ##########
##########    ##########    ##########    ##########
##########    ##########    ##########    ##########
##########    ##########    ##########    ##########

【样例 2 解释】

可能含有机器人的位置为：

##########
#x#.xxx..#
#x#xxxxx.#
#xxxxxxxx#
#x#xxxxx.#
#x#.xxx..#
##########
##########
##########
##########

【样例 3 解释】

可能含有机器人的位置为：

##########
#xx#.....#
#xx#.....#
#xxx.....#
#xx#.....#
#x.#.....#
##########
##########
##########
##########

【数据规模与约定】

对于$ 10\% $的测试数据(测试点$ 4\sim5 $)，满足 $ D = 10^9 $。

另有$ 15\% $的测试数据(测试点$ 6\sim8 $)，满足 $ D = 1 $。

另有$ 20\% $的测试数据(测试点$ 9\sim12 $)，满足 $ N \le 100 $。

对于$ 100\% $的测试数据，均满足上文所给出的数据规模。

【来源】

USACO 十二月月赛 Gold 组