Почему крокодилы не летают?
На остров Робинзона выползли погреться на солнышке и задремали несколько крокодилов. Робинзон хочет прогнать неприятных соседей, не поднимая шума. Для этого он кидает в дремлющих крокодилов орехи.
В каждой клетке острова находится не более одного крокодила. Напуганный орехом крокодил быстро бежит строго по прямой, пока не окажется в воде. Для каждого крокодила известно направление, в котором он побежит, если его напугать. Направления, в которых будут убегать крокодилы, параллельны сторонам острова.
Если на пути напуганного крокодила окажется другой крокодил, то, столкнувшись, они разозлятся, и нападут на Робинзона. Поэтому надо тщательно выбирать очередного крокодила, чтобы на его пути были только пустые клетки.
Робинзон не кидает очередной орех, пока предыдущий крокодил не окажется в воде.
Требуется написать программу, определяющую максимальное количество крокодилов, которых можно прогнать, не разозлив их.
В первой строке входного файла записаны числа n и m — размеры острова с севера на юг и с запада на восток. Последующие n строк по m символов в каждой описывают текущее расположение крокодилов на острове. Если клетка свободна, то она обозначается точкой «.», а если там находится крокодил, то в ней указано направление, в котором побежит этот крокодил. Направления обозначаются буквами: «N» — север, «S» — юг, «E» — восток, «W» — запад
Выходной файл должен содержать одно число — максимальное количество крокодилов, которых можно прогнать, не разозлив.
Данная задача содержит три подзадачи. Для оценки каждой подзадачи используется своя группа тестов. Баллы за подзадачу начисляются только в том случае, если все тесты из этой группы пройдены.
1 <= $n$, $m$ <= 30. Подзадача оценивается в 30 баллов.
1 <= $n$, $m$ <= 500. Подзадача оценивается в 30 баллов.
1 <= $n$, $m$ <= 2000. Подзадача оценивается в 40 баллов.
Рисунок к третьему примеру
1 1 .
0
1 1 W
1
5 7 ....... ...S... ..WE... ...N... .......
2