eolymp
bolt
Try our new interface for solving problems
Məsələlər

Наутилус

Наутилус

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

Наутилус - это секретная подводная лодка, плывущая по океану и пытающаяся скрыться.

Океан моделируется таблицей r * c символов, где через "#" обозначен остров, а ччерез "." обозначена вода. Например:

prb9620.gif

Каждую минуту Наутилус издает радиосигнал, который указывает направление, в котором будет передвигаться подлодка. Направление всегда одно из следующих: север (N), восток (E), юг (S), запад (W), как показано на рисунке выше справа.

Витаутас построил радар, который перехватывает периодические подводные сигналы. За последние m минут радар собрал m радиосигналов, представленных в виде последовательности m символов, например "WS?EE??". Некоторые сигналы не могут быть декодированы, они помечены как "?".

Витаутас не знает начального местоположения подводной лодки, но хочет использовать карту океана, чтобы определить ее текущее местоположение. Учитывая, что Наутилус всегда находится в клетках воды на карте, помогите Витаутасу рассчитать количество различных клеток, в которых Наутилус может находиться в настоящее время.

Giriş verilənləri

Первая строка содержит три целых числа r, c, m (1r, c500, 1m5000). Следующие r строк содержат таблицу r * c из символов "#" и "." представляющих карту океана. Последняя строка содержит последовательность сигналов, перехваченных Витаутасом - строку из m символов, принадлежащих множеству {N, E, S, W, ?}.

Çıxış verilənləri

Выведите единственное целое число - количество возможных различных текущих позиций Наутилуса.

Nümunə

Giriş verilənləri #1
5 9 7
...##....
..#.##..#
..#....##
.##...#..
....#....
WS?EE??
Çıxış verilənləri #1
22
Mənbə 2019 Baltic Olympiad in Informatics, День 1, 27 Апр - 2 Май