Description

A consequence of watching too many mechanical DIY videos online is that Farmer John accidentally built a robot on his farm that can replicate itself.

The farm can be represented as an $N \times N$ square grid ($3 \le N \le 1000$). Each cell is either empty or contains a rock, and all boundary cells contain rocks. Some empty cells are marked as possible starting positions for the robot.

Farmer John initially places the robot on one of the possible starting positions. After that, every hour, all copies of the robot move one cell in the same direction: north, south, east, or west. After every $D$ hours ($1 \le D \le 10^9$), each copy of the robot replicates itself: a robot replicating at cell $(x, y)$ creates new copies at $(x+1, y)$, $(x-1, y)$, $(x, y+1)$, and $(x, y-1)$; the original robot remains at $(x, y)$. After some time, there may be multiple robots in the same cell.

If moving or replicating would cause any robot to crash into a rock, then all robots immediately stop moving. Note that this means all robots will eventually stop, since the boundary of the farm is made of rocks.

Help the cows compute the number of empty cells that could contain a robot at some moment.

Input Format

The first line contains two space-separated integers $N$ and $D$. The next $N$ lines each contain $N$ characters. Each character is one of '.', 'S', and '#'. Both '.' and 'S' represent an empty cell, and 'S' represents a possible robot starting position. '#' represents a rock.

All characters in the first row, last row, first column, and last column are '#'.

Output Format

Output one integer, the number of cells that could contain a robot at some moment.

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

15

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

28

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

10

Hint

Explanation for Sample 1:

In the diagram below, x represents a robot.

The cells that could contain a robot are:

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

Here is one possible sequence of events:

FJ places the robot at the upper-left starting position. The robot moves one unit to the right. The robot replicates itself. All robots move one unit to the right. Replicating again would cause some robot to crash into a rock, so the process stops.

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

Explanation for Sample 2:

The cells that could contain a robot are:

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

Explanation for Sample 3:

The cells that could contain a robot are:

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

Testdata Properties:

• Testdata 4-5 satisfy $D = 10^9$.
• Testdata 6-8 satisfy $D = 1$.
• Testdata 9-12 satisfy $N \le 100$.
• Testdata 13-20 have no additional constraints.

Problem by: Benjamin Qi.

Translated by ChatGPT 5