Реплікація#10370

Реплікація

1 секунда

128 мегабайтів

Складна

Фермер Джон, надивившись відео про "зроби сам", випадково випустив самовідтворювального робота на своїй фермі!

Ферма зображена у вигляді сітки розміром $n \times n$ n \times n, де кожна клітинка може бути або порожньою, або заповненою каменем, причому всі граничні клітинки заповнені каменем. Деякі з порожніх клітинок позначені як можливі стартові позиції для робота.

Спочатку фермер Джон розміщує робота в одній з можливих стартових позицій. Щогодини всі копії робота рухаються в одному напрямку: на північ, південь, схід або захід. Кожні $d$ годин кожна копія робота реплікується — робот у клітинці $(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)$ . З часом кілька роботів можуть опинитися в одній клітинці.

Якщо переміщення або реплікація змусить будь-якого з роботів потрапити на камінь, всі роботи негайно вимикаються. Зверніть увагу, що роботи зрештою вимкнуться через те, що межі ферми кам'яні.

Допоможіть коровам підрахувати кількість порожніх клітинок, які можуть бути зайняті роботом у будь-який момент часу.

Вхідні дані

Перший рядок містить два цілі числа $n$ ( $3 \leq n \leq 1000$ 3 \le n \le 1000) і $d$ ( $1 \leq d \leq 1 0^{9}$ 1 \le d \le 10^9). Кожен з наступних $n$ рядків містить $n$ символів. Кожен символ може бути '.', 'S' або '#'. Символи '.' і 'S' позначають порожні клітинки, 'S' позначає можливу стартову позицію для робота. Символ '#' позначає камінь.

Усі символи в першому і останньому рядку, а також у першому і останньому стовпці дорівнюють '#'.

Вихідні дані

Виведіть одне ціле число — кількість клітинок, які в якийсь момент часу можуть містити робота.

Приклади

На наступних діаграмах $x$ позначають роботів. Місця, які можуть бути зайняті роботами:

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

Розглянемо одну з можливих послідовностей подій:

Фермер Джон поміщає робота в крайнє ліве початкове положення.
Робот переміщується на одну одиницю вправо.
Робот реплікується.
Усі роботи переміщуються на одну одиницю вправо.
Друга реплікація призведе до того, що копія робота переміститься в скелю, тому процес завершується.

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

Приклад 1

Приклад 2