Помогите решить задачу по програмированию на с++

Question

Помогите решить задачу по програмированию на с++

А.М. Ученик (206), закрыт 10 часов назад

Робинзон живет на острове, который представляет собой прямоугольник размером
n
×
m
клеток.

На остров Робинзона выползли погреться на солнышке и задремали несколько крокодилов. Робинзон хочет прогнать неприятных соседей, не поднимая шума. Для этого он кидает в дремлющих крокодилов орехи.

В каждой клетке острова находится не более одного крокодила. Напуганный орехом крокодил быстро бежит строго по прямой, пока не окажется в воде. Для каждого крокодила известно направление, в котором он побежит, если его напугать. Направления, в которых будут убегать крокодилы, параллельны сторонам острова.

Если на пути напуганного крокодила окажется другой крокодил, то, столкнувшись, они разозлятся, и нападут на Робинзона. Поэтому надо тщательно выбирать очередного крокодила, чтобы на его пути были только пустые клетки.

Робинзон не кидает очередной орех, пока предыдущий крокодил не окажется в воде.

Требуется написать программу, определяющую максимальное количество крокодилов, которых можно прогнать, не разозлив их.

Формат входных данных
В первой строке входного файла записаны числа
n
и
m
"— размеры острова с севера на юг и с запада на восток (
1
≤
n
,

m
≤
2000
).

Последующие
n
строк по
m
символов в каждой описывают текущее расположение крокодилов на острове.

Если клетка свободна, то она обозначается точкой «.», а если там находится крокодил, то в ней указано направление, в котором побежит этот крокодил. Направления обозначаются буквами: «N» "— север, «S» "— юг, «E» "— восток, «W» "— запад.

Формат выходных данных
Выходной файл должен содержать одно число "— максимальное количество крокодилов, которых можно прогнать, не разозлив.

Answer 1

gpt для слабых, мы юзаем для такого ответы маил

Answer 2

Совершенно неэффективное решение:

 #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;
}