Репликация
В результате просмотра слишком большого количества видео по технике "сделай сам" в сети, фермер Джон случайно выпустил самовоспроизводящегося робота на своей ферме!
Ферма представляется сеткой n × n, где каждая ячейка либо пуста, либо заполнена камнем, а все граничные квадраты заполнены камнем. Некоторые ячейки, не являющиеся каменными, обозначены как возможные стартовые места для робота.
Фермер Джон сначала ставит робота на одну из возможных стартовых позиций. В каждый последующий час все копии робота движутся одной скоординированной массой в одном направлении: на север, юг, восток или запад. Через каждые d часов каждая копия робота реплицируется - робот в ячейке (x, y) создает новые копии в ячейках (x + 1, y), (x − 1 , y), (x, y + 1) и (x, y − 1); исходный робот остается в (x, y). Со временем несколько роботов могут занять одну и ту же ячейку.
Если перемещение или репликация заставит любого из роботов переместиться в скалу, то все роботы немедленно отключатся. Обратите внимание, что роботы должны в конечном итоге выключиться из-за того, что граница фермы скалистая.
Помогите коровам вычислить количество пустых квадратов, которые потенциально могут в какой-то момент времени содержать робота.
Входные данные
Первая строка содержит два целых числа n (3 ≤ n ≤ 1000) и d (1 ≤ d ≤ 10^9). Каждая из следующих n строк ввода содержит n символов. Каждый символ может быть одним из символов '.', 'S' или '#'. '.' и 'S' обозначают пустые ячейки, 'S' обозначает возможную начальную позицию для робота. '#' обозначает камень.
Все символы в первой и последней строке, а также в первом и последнем столбце равны '#'.
Выходные данные
Выведите одно целое число - количество ячеек, которые в какой-то момент времени могут содержать робота.
Пример
На следующих диаграммах x обозначают роботов. Места, которые могут быть заняты роботами:
########## #xxx.....# #xxxx....# #xxx.....# ########## #xx..xxx.# ########## ########## ########## ##########
Рассмотрим одну из возможных последовательностей событий:
ФД помещает робота в крайнее левое начальное положение.
Робот перемещается на одну единицу вправо.
Робот реплицирует.
Все роботы перемещаются на одну единицу вправо.
Вторая репликация приведет к тому, что копия робота переместится в скалу, поэтому процесс завершается.
########## ########## ########## ########## #........# #........# #.x......# #..x.....# #x.......# #.x......# #xxx.....# #.xxx....# #........# #........# #.x......# #..x.....# ########## -> ########## -> ########## -> ########## #........# #........# #........# #........# ########## ########## ########## ########## ########## ########## ########## ########## ########## ########## ########## ########## ########## ########## ########## ##########