@alex_l2005

ABCPascal.Net. Олимпиадная задача, как ускорить код?

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

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

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

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

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

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

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

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

Пример 1
Ввод
1 5
WN.SE
Вывод
4

Пример 2
Ввод
1 3
E.W
Вывод
0

Пример 3
Ввод
3 4
.N.W
WWSS
EWEW
Вывод
4

Подскажите, пожалуйста, как ускорить код? Часть тестов код проходит правильно, а остальное - TL (Time Limit). Как ускорить выполнение код, чтобы не было TL?
var
  c, r, rows, cols, row, col, count, pred: integer;
  a: array [,] of Integer;
  Yes: boolean;
  s: string;

begin
  readln(rows, cols);  
  Setlength(a, rows, cols);
  
  for row := 0 to rows - 1 do
  begin
    Readln(s);
    for col := 0 to cols - 1 do
      case s[col + 1] of
        '.': a[row, col] := 0;
        'N': a[row, col] := 1;
        'S': a[row, col] := 2;
        'E': a[row, col] := 3;
        'W': a[row, col] := 4;
      end;
  end;
  
  count := 0;
  repeat
    pred := count;    
    for row := 0 to rows - 1 do
      for col := 0 to cols - 1 do
        if a[row, col] > 0 then
        begin
          Yes := True;
          case a[row, col] of
            1:
              for r := row - 1 downto 0 do // N : row-1
                if a[r, col] > 0 Then
                begin
                  Yes := False;
                  break;
                end;
            
            2:
              for r := row + 1 to rows - 1 do // S : row+1            
                if a[r, col] > 0 Then
                begin
                  Yes := False;
                  break;  
                end;
            
            3:
              for c := col + 1 to cols - 1 do // E : col+1 
                if a[row, c] > 0 Then
                begin
                  Yes := False;
                  break;   
                end;
            
            4:
              for c := col - 1 downto 0 do // W : col-1
                if a[row, c] > 0 Then
                begin
                  Yes := False;
                  break;
                end;
          end;
          if Yes then 
          begin
            a[row, col] := 0; 
            count += 1; 
          end;
        end;
    
    if pred = count then Break;
  until False;
  
  writeln(count);
end.


Протестировать решение: https://contest.yandex.ru/roi/contest/999/enter
  • Вопрос задан
  • 1282 просмотра
Пригласить эксперта
Ответы на вопрос 3
@evgeniy_lm
Попробуй рекурсию.
Берешь первого попавшегося крокодила (любого). Смотришь нет ли на его пути других и пытаешься убрать их и так до самого последнего. Самое главное нужно предусмотреть обработку зацикливания как во втором примере.

У тебя должно получится что-то типа
procedure TestCroco(row, col)
begin
if a[row, col] = 0 then Exit;
..............
end;

for row := 0 to rows - 1 do
for col := 0 to cols - 1 do
TestCroco(row, col);

ЗЫ Могу сделать за символическую плату плату
Ответ написан
Комментировать
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
У вас не правильный, медленный алгоритм.

Вы каждый раз, после убранного крокодила, ищете нового крокодила по всему полю, делая все проверки. Это медленно. Можно проверки делать ровно один раз для каждого крокодила:

1) Пронумеруйте всех крокодилов. Рекомендую в новой матрице записать 0 для пустоты и номер крокодила, где такой есть.

2) Как у вас уже сделано, для всех крокодилов в нужном направлении смотрите все клетки, но не останавливайтесь на первом встречном крокодиле. Продолжайте движение и считайте всех встреченных крокодилов. Таким образом вы для каждого крокодила узнаете, скольких надо прогнать перед ним.

Сразу же, сложите всех крокодилов со счетчиком 0 (которых уже можно прогонять прямо сейчас) в очередь. Прогоняйте крокодилов из очереди, пока она не пуста. При обработке такого крокодила - считайте его в ответе, сотрите его из матрицы, и, что важно, обновите счетчики для всех крокодилов, которым он мешал. Для этого от текущего крокодила пройдитесь во ВСЕ стороны и, если крокодил там идет вам навстречу и еще не убран, уменьшите его счетчик. Если счетчик стал равен 0, добавьте этого крокодила в очередь. Все.

Это решение за O(n^3), а ваше - за O(n^4).

Получается что-то вроде обхода в ширину на графе крокодилов. Можно было бы все ребра подсчитать сначала (сделать списки кто кому мешает), но эти списки суммарно будут N^3 памяти занимать, что может не влезть в память, а на скорость работы принципиально не влияет (ну, в 4 раза ускорит, где-то). Если опять не пройдет по времени, а по памяти куб у вас влезает, то постройте граф и при удалении крокодила не в матрице ищите, кому он мешает, а уже в графе пройдитесь по списку смежных вершин.
Ответ написан
Комментировать
@Andy_U
У вас задача на тему топологической сортировки: По ссылке stackoverflow.com/questions/4620100/partial-order-... есть код на питоне, котрый останавливается, как только все что можно, отсортировывается. Т.е. когда остаются лишь циклы. Вот и вам надо имплементировать что-то типа этого. Вроде бы сложность O(сумма нод + сумма ребер графа). Плюс сложность построения самого графа.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы