Problem Description

After watching too many mechanical DIY videos online, Farmer John accidentally created a self-replicating robot on his farm!

The farm can be represented by an $N \times N$ matrix ($3 \leq N \leq 1000$), where each cell is either empty or contains a rock, and all boundary cells are rocks. Some empty cells are designated as possible starting positions for the robot.

Farmer John initially places the robot at one of the possible starting positions. In each subsequent hour, all copies of the robot move one cell in the same direction: north, south, east, or west. Every $D$ hours ($1 \leq D \leq 10^9$), each copy of the robot replicates itself—a robot replicating at cell $(x, y)$ will create new copies at cells $(x+1, y)$, $(x-1, y)$, $(x, y+1)$, and $(x, y-1)$; the original robot remains at $(x, y)$. Over time, multiple robots may be present in the same cell.

If moving or replicating would cause any robot to hit a rock, all robots immediately stop moving. Note that this means all robots will eventually stop, as the boundaries of the farm are rocks.

Help the cows determine the number of empty cells that may contain a robot at some point.

Input Format

The first line of input contains two space-separated integers $N$ and $D$. The following $N$ lines each contain $N$ characters. Each character is either '.', 'S', or '#'. '.' and 'S' both indicate empty cells, with 'S' indicating a possible starting position. '#' indicates a rock.

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

Output Format

Output a single integer, the number of cells that may contain a robot at some point.

Sample Input and Output

Input Sample #1

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

Output Sample #1

15

Input Sample #2

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

Output Sample #2

28

Input Sample #3

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

Output Sample #3

10

Notes/Hints

Sample 1 Explanation:

In the following diagrams, 'x' represents a robot.

Possible positions containing robots are:

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

A possible sequence of events is:

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.
Another replication would cause a robot to hit a rock, so the process stops.

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

Sample 2 Explanation:

Possible positions containing robots are:

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

Sample 3 Explanation:

Possible positions containing robots are:

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

Test Case Properties:

• Test cases 4-5 satisfy $D = 10^9$.
• Test cases 6-8 satisfy $D = 1$.
• Test cases 9-12 satisfy $N \leq 100$.
• Test cases 13-20 have no additional restrictions.

Contributed by: Benjamin Qi

见题面 Input 部分

见题面 Output 部分