Задача Y - 2020. Робинзон и крокодилы
Автор задачи: Всероссийская олимпиада школьников по информатике
Первоисточник: Пробный тур регионального этапа 2017
Задачу добавил: alef
Успешно сдано решений: 338
|
Ограничение по времени: |
2 секунды |
|
Ограничение по памяти: |
512 мегабайт |
Робинзон живет на острове, который представляет собой прямоугольник размером n × m клеток.
На остров Робинзона выползли погреться на солнышке и задремали несколько крокодилов. Робинзон хочет прогнать неприятных соседей, не поднимая шума. Для этого он кидает в дремлющих крокодилов орехи.
В каждой клетке острова находится не более одного крокодила. Напуганный орехом крокодил быстро бежит строго по прямой, пока не окажется в воде. Для каждого крокодила известно направление, в котором он побежит, если его напугать. Направления, в которых будут убегать крокодилы, параллельны сторонам острова.
Если на пути напуганного крокодила окажется другой крокодил, то, столкнувшись, они разозлятся, и нападут на Робинзона. Поэтому надо тщательно выбирать очередного крокодила, чтобы на его пути были только пустые клетки.
Робинзон не кидает очередной орех, пока предыдущий крокодил не окажется в воде.
Требуется написать программу, определяющую максимальное количество крокодилов, которых можно прогнать, не разозлив их.
Формат входных данных
В первой строке входных данных записаны числа n и m — размеры острова с севера на юг и с запада на восток. Последующие n строк по m символов в каждой описывают текущее расположение крокодилов на острове. Если клетка свободна, то она обозначается точкой «.», а если там находится крокодил, то в ней указано направление, в котором побежит этот крокодил. Направления обозначаются буквами: «N» — север, «S» — юг, «E» — восток, «W» — запад.
Формат выходных данных
Требуется вывести одно число — максимальное количество крокодилов, которых можно прогнать, не разозлив.
Примеры входных и выходных данных
|
входные данные |
выходные данные |
|
1 5 WN.SE |
4 |
|
1 3 E.W |
0 |
|
3 4 .N.W WWSS EWEW |
4 |
Пояснение к примеру
Рисунок показывает исходное расположение крокодилов в третьем примере.
Описание подзадач и системы оценивания
Данная задача содержит три подзадачи. Баллы за подзадачу начисляются только в том случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.
|
Подзадача |
Баллы |
Дополнительные ограничения |
Необходимые подзадачи |
Информация о проверке |
|
n, m |
||||
|
1 |
30 |
1 ≤ n, m ≤ 30 |
|
полная |
|
2 |
30 |
1 ≤ n, m ≤ 500 |
1 |
полная |
|
3 |
40 |
1 ≤ n, m ≤ 2000 |
1, 2 |
полная |