Фермер Джон сделал робота!
Ферма может быть представлена решёткой \(N\times N\) (\(3\le N\le 1000\)),
где каждая ячейка решётки или пустая или заполнена скалой и все граничные
ячейки заполнены скалой. Некоторые пустые ячейки определены как возможные
стартовые позиции робота.
ФД изначально располагает робота на одной из возможных стартовых позиций.
В каждый последующий час все копии робота как одна скоординированная масса
двигаются в некотором направлении - на север, юг, запад или восток.
После \(D\) часов (\(1 \leq D \leq 10^9\)), каждая копия робота реплицируется
--- робот в ячейке \((x,y)\) который реплицируется, создаёт новые копии в ячейках
\((x+1,y)\), \((x-1,y)\), \((x,y+1)\), \((x,y-1)\); оригинальный робот остаётся в ячейке
\((x,y)\). После некоторого времени много роботов могут занять одну и ту же ячейку.
Если движение или репликация приведут к тому, что робот врежется в скалу,
тогда все роботы незамедлительно останавливаются. Заметим, из этого следует,
что роботы обязательно когда-то остановятся, поскольку граница фермы вся из скалы.
Помогите коровам вычислить количество пустых квадратов, которые потенциально
в некоторый момент времени смогут содержать робота.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит два разделённых пробелом целых числа
\(N\) и
\(D\).
Каждая из следующих
\(N\) строк содержит по
\(N\) символов. Каждый символ -
один из '.', 'S', '#'. '.' и 'S' представляют пустые ячейки, причём 'S'
обозначает возможную стартовую позицию робота. '#' обозначает скалу.
Все символы в первой и последней строке, в первом и последнем столбце - '#'.
ФОРМАТ ВЫВОДА (на экран / stdout):
Одно целое число, содержащее количество ячеек, которые могут в некоторый момент
времени содержать робота.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10 1
##########
#........#
#S.......#
#........#
##########
#S....S..#
##########
##########
##########
##########
|
15
|