3635. [USACO 21Dec]复制

【题目描述】

在网上观看太多机械 DIY 视频的后果就是，Farmer John 偶然在他的农场上制造了一个可以自我复制的机器人！农场可以用一个 N×NN×N 的方阵表示（3≤N≤10003≤N≤1000），其中每个方格是空的或有岩石，并且所有边界上的方格均有岩石。某些没有岩石的方格被指定为机器人可能的起始位置。

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

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

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

【输入格式】

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

【输出格式】

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

【样例输入】

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

【样例输出】

15

【样例说明】

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

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

##########

#xxx.....#

#xxxx....#

#xxx.....#

##########

#xx..xxx.#

##########

##########

##########

##########

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

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

##########    ##########    ##########    ##########

#........#    #........#    #.x......#    #..x.....#

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

#........#    #........#    #.x......#    #..x.....#

##########  -> ##########  -> ##########  -> ##########

#........#    #........#    #........#    #........#

##########    ##########    ##########    ##########

##########    ##########    ##########    ##########

##########    ##########    ##########    ##########

##########    ##########    ##########    ##########

【数据规模与约定】

测试点 4-5 满足 D=10^9。

测试点 6-8 满足 D=1。

测试点 9-12 满足 N≤100N≤100。

测试点 13-20 没有额外限制。

【来源】

USACO 2021年十二月公开赛 Gold 组