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