Помогите решить задачу по програмированию на с++
Робинзон живет на острове, который представляет собой прямоугольник размером
n
×
m
клеток.
На остров Робинзона выползли погреться на солнышке и задремали несколько крокодилов. Робинзон хочет прогнать неприятных соседей, не поднимая шума. Для этого он кидает в дремлющих крокодилов орехи.
В каждой клетке острова находится не более одного крокодила. Напуганный орехом крокодил быстро бежит строго по прямой, пока не окажется в воде. Для каждого крокодила известно направление, в котором он побежит, если его напугать. Направления, в которых будут убегать крокодилы, параллельны сторонам острова.
Если на пути напуганного крокодила окажется другой крокодил, то, столкнувшись, они разозлятся, и нападут на Робинзона. Поэтому надо тщательно выбирать очередного крокодила, чтобы на его пути были только пустые клетки.
Робинзон не кидает очередной орех, пока предыдущий крокодил не окажется в воде.
Требуется написать программу, определяющую максимальное количество крокодилов, которых можно прогнать, не разозлив их.
Формат входных данных
В первой строке входного файла записаны числа
n
и
m
"— размеры острова с севера на юг и с запада на восток (
1
≤
n
,
m
≤
2000
).
Последующие
n
строк по
m
символов в каждой описывают текущее расположение крокодилов на острове.
Если клетка свободна, то она обозначается точкой «.», а если там находится крокодил, то в ней указано направление, в котором побежит этот крокодил. Направления обозначаются буквами: «N» "— север, «S» "— юг, «E» "— восток, «W» "— запад.
Формат выходных данных
Выходной файл должен содержать одно число "— максимальное количество крокодилов, которых можно прогнать, не разозлив.
gpt для слабых, мы юзаем для такого ответы маил
Совершенно неэффективное решение:
#include <iostream>
#include <vector>
#include <limits>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
cin.ignore(numeric_limits<streamsize>::max(), '\n');
vector<string> t(n);
for (auto &s: t) { getline(cin, s); }
bool flg;
do {
int i, j, k;
flg = false;
// Обработка горизонталей
for (i = 0; i < n; ++i) {
// Удаляем крокодилов, способных убежать на запад
for (j = 0; j < m && (t[i][j] == '.' || t[i][j] == 'W'); ++j) {
flg |= t[i][j] == 'W';
t[i][j] = '.';
}
// Удаляем крокодилов, способных убежать на восток
for(k = m - 1; k >= j && (t[i][k] == '.' || t[i][k] == 'E'); --k) {
flg |= t[i][k] == 'E';
t[i][k] = '.';
}
}
// Обработка вертикалей
for (i = 0; i < m; ++i) {
// Удаляем крокодилов, способных убежать на север
for (j = 0; j < n && (t[j][i] == '.' || t[j][i] == 'N'); ++j) {
flg |= t[j][i] == 'N';
t[j][i] = '.';
}
// Удаляем крокодилов, способных убежать на юг
for(k = n - 1; k >= j && (t[k][i] == '.' || t[k][i] == 'S'); --k) {
flg |= t[k][i] == 'S';
t[k][i] = '.';
}
}
} while (flg); // хотя бы один крокодил убежал и надо проверить оставшихся
// подсчёт оставшихся крокодилов
int cnt = 0;
for (auto &s: t) { for (auto ch: s) { cnt += ch != '.'; }}
cout << cnt;
} 