Задача №536. Монстры
- выключить голову;
- написать тупой перебор и сдать его;
- включить голову;
- придумать решение задачи и закодить его;
- написать генератор тестов;
- запустить на многих тестах тупой перебор и умное решение;
- если стресс-тестирование нашло антитест к умному решению, то найти ошибку в умном решении, исправить её и перейти к предыдущему пункту;
- сдать код, в котором вызывается тупое решение, если ограничения маленькие, и умное решение, если ограничения большие.
Таким образом, по каждой задаче необходимо получить +1.
В одной секретной лаборатории вывели новый вид маленьких монстров, размером чуть больше суслика. В ходе исследований ученые решили поставить следующий эксперимент. В центре комнаты устанавливается прямоугольный стол, поверхность которого разбита на \(N\) х \(M\) клеток размера 1 х 1. В начальный момент времени на некоторых его клетках располагаются монстры, смотрящие параллельно сторонам стола. По команде экспериментатора монстры начинают двигаться по прямой в ту сторону, в которую они смотрят, доходят до края стола и спрыгивают на пол. Там их собирает лаборант Петя и относит в клетку.
В первой строке вводятся числа \(M\) и \(N\) - размеры лабораторного стола (1 <= \(M\), N <= \(10^6\)). В следующей строке задается число \(K\) - количество монстров (0 <= \(K\) <= \(10^3\)). Следующие \(K\) строк содержат описания монстров - два целых числа и один символ из множества {\(N\), \(E\), \(S\), \(W\)} - начальные координаты и направление соответствующего монстра (соответствие направлений и координат приведено на рисунке 1). Символ отделен от чисел ровно одним пробелом.
Выведите единственное число - количество клеток стола, на которых побывают монстры.
Пример соответствует расположению монстров, приведенному на рисунке 1.монстры.
8 5 4 4 4 S 6 2 W 6 3 N 6 4 S
13