Replication

题目描述

由于在网上看了太多“自己动手做工程”的视频带来的不幸后果，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' 表示机器人可能的起始位置。'#' 表示岩石。 第一行与最后一行、第一列与最后一列中的所有字符均为 '#'.

输出格式

输出一个整数，表示在某个时刻可能被机器人占据的格子数量。

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

15

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

28

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

10

提示

在下面的图中，x 表示机器人。 可能被机器人占据的位置： ########## #xxx.....# #xxxx....# #xxx.....# ########## #xx..xxx.# ########## ########## ########## ########## 一种可能的事件序列如下： FJ 将机器人放在最左上角的起始位置。 机器人向右移动一格。 机器人复制。 所有机器人向右移动一格。 再进行一次复制将导致某个机器人的副本进入岩石，因此过程终止。 ########## ########## ########## ########## #........# #........# #.x......# #..x.....# #x.......# #.x......# #xxx.....# #.xxx....# #........# #........# #.x......# #..x.....# ########## -> ########## -> ########## -> ########## #........# #........# #........# #........# ########## ########## ########## ########## ########## ########## ########## ########## ########## ########## ########## ########## ########## ########## ########## ########## 可能被机器人占据的位置： ########## #x#.xxx..# #x#xxxxx.# #xxxxxxxx# #x#xxxxx.# #x#.xxx..# ########## ########## ########## ########## 可能被机器人占据的位置： ########## #xx#.....# #xx#.....# #xxx.....# #xx#.....# #x.#.....# ########## ########## ########## ########## 计分（SCORING）： 测试点 4-5 满足 $D=10^9$。 测试点 6-8 满足 $D=1$。 测试点 9-12 满足 $N\le 100$。 测试点 13-20 无额外限制。 题目致谢：Benjamin Qi

标签: USACO|2020|Gold

来源

USACO|2020|Gold