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