#PU1065. USACO 2020 December Contest, Gold — Problem 1. Replication

    ID: 1183 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>USACO赛事:dec20来源:usaco.orgscoring:equal_test_cases模拟枚举

USACO 2020 December Contest, Gold — Problem 1. Replication

USACO 2020 December Contest, Gold — Problem 1. Replication

题目描述

The ill-fated result of watching too many "do it yourself" engineering videos on the web, Farmer John has accidentally released a self-replicating robot on his farm! The farm can be represented by an N×NN\times N grid (3≤N≤10003\le N\le 1000) where each grid cell is either empty or filled with rock, and all border squares are filled with rock. Some non-rock cells are designated as possible starting locations for the robot. Farmer John initially places the robot at one of the possible starting positions. In every hour that follows, all copies of the robot move in one coordinated mass in the same direction, either north, south, east, or west. After every DD hours (1≤D≤1091 \leq D \leq 10^9), every copy of the robot replicates --- a robot at cell (x,y)(x,y) that replicates creates new copies in cells (x+1,y)(x+1,y), (x−1,y)(x-1,y), (x,y+1)(x,y+1), and (x,y−1)(x,y-1); the original robot remains at (x,y)(x,y). Over time, multiple robots might come to occupy the same cell. If moving or replicating would cause any of the robots to move into a rock, then all robots shut down immediately. Note that this implies that the robots must eventually shut down, due to the border of the farm being rock. Help the cows figure out the number of empty squares that could potentially at some point in time hold a robot.

输入格式

The first line contains two space-separated integers NN and DD. The next NN lines of input each contain NN characters. Each character is one of '.', 'S', or '#'. '.' and 'S' both represent empty cells, with 'S' denoting a possible starting position for the robot. '#' denotes a rock. All characters in the first and last row and first and last column are '#'.

输出格式

An integer counting the number of cells that could at some point in time hold a robot.

数据范围

Test cases 4-5 satisfy D=109D=10^9. Test cases 6-8 satisfy D=1D=1. Test cases 9-12 satisfy N≤100N\le 100. Test cases 13-20 satisfy no additional constraints. Problem credits: Benjamin Qi

样例

样例 1

10 1
##########
#........#
#S.......#
#........#
##########
#S....S..#
##########
##########
##########
##########
15
In the following diagrams, x's denote robots.
Locations that could be occupied by robots:
##########
#xxx.....#
#xxxx....#
#xxx.....#
##########
#xx..xxx.#
##########
##########
##########
##########
One possible sequence of events could be as follows:
FJ places the robot at the upper-left-most starting position.
The robot moves one unit to the right.
The robot replicates.
All robots move one unit to the right.
Another replication would cause a copy of the robot to move into a rock, so
the process terminates.
##########    ##########    ##########    ##########
#........#    #........#    #.x......#    #..x.....#
#x.......#    #.x......#    #xxx.....#    #.xxx....#
#........#    #........#    #.x......#    #..x.....#
########## -> ########## -> ########## -> ##########
#........#    #........#    #........#    #........#
##########    ##########    ##########    ##########
##########    ##########    ##########    ##########
##########    ##########    ##########    ##########
##########    ##########    ##########    ##########

样例 2

10 2
##########
#.#......#
#.#......#
#S.......#
#.#......#
#.#......#
##########
##########
##########
##########
28
Locations that could be occupied by robots:
##########
#x#.xxx..#
#x#xxxxx.#
#xxxxxxxx#
#x#xxxxx.#
#x#.xxx..#
##########
##########
##########
##########

样例 3

10 2
##########
#.S#.....#
#..#.....#
#S.......#
#..#.....#
#..#.....#
##########
##########
##########
##########
10
Locations that could be occupied by robots:
##########
#xx#.....#
#xx#.....#
#xxx.....#
#xx#.....#
#x.#.....#
##########
##########
##########
##########