| Автор: | Жюри XXVI Всероссийской олимпиады школьников по информатике | Ограничение времени: | 2 сек | |
| Входной файл: | alligator.in | Ограничение памяти: | 256 Мб | |
| Выходной файл: | alligator.out |
Робинзон живет на острове, который представляет собой прямоугольник размером n × m клеток.
На остров Робинзона выползли погреться на солнышке и задремали несколько крокодилов. Робинзон хочет прогнать неприятных соседей, не поднимая шума. Для этого он кидает в дремлющих крокодилов орехи.
В каждой клетке острова находится не более одного крокодила. Напуганный орехом крокодил быстро бежит строго по прямой, пока не окажется в воде. Для каждого крокодила известно направление, в котором он побежит, если его напугать. Направления, в которых будут убегать крокодилы, параллельны сторонам острова.
Если на пути напуганного крокодила окажется другой крокодил, то, столкнувшись, они разозлятся, и нападут на Робинзона. Поэтому надо тщательно выбирать очередного крокодила, чтобы на его пути были только пустые клетки.
Робинзон не кидает очередной орех, пока предыдущий крокодил не окажется в воде.
Требуется написать программу, определяющую максимальное количество крокодилов, которых можно прогнать, не разозлив их.
В первой строке входного файла записаны числа n и m — размеры острова с севера на юг и с запада на восток. Последующие n строк по m символов в каждой описывают текущее расположение крокодилов на острове. Если клетка свободна, то она обозначается точкой, а если там находится крокодил, то в ней указано направление, в котором побежит этот крокодил. Направления обозначаются буквами: N — север, S — юг, E — восток, W — запад.
Выходной файл должен содержать одно число — максимальное количество крокодилов, которых можно прогнать, не разозлив.
1 ≤ n,m ≤ 2000.
| № | Входной файл (alligator.in) |
Выходной файл (alligator.out) |
|---|---|---|
| 1 |
|
|
| 2 |
|
|
| 3 |
|
|