Разбор задачи B. Великий пожар Анк-Морпорка

Тема: поиск в ширину
Сложность: средняя

Для решения задачи необходимо использовать известный алгоритм поиска в ширину. Для лучшего понимания алгоритма рекомендуется рассмотреть разбор задач 741. Ход конем и 1509. Очистка озера.

Дополнительно можно воспользоваться следующими оптимизациями: 1) окружить поле клетками с '.'; 2) свести задачу к одному измерению (т.е. текущее состояние будет описываться одним целым числом).
Объявление необходимых структур данных:

var n,m:integer; { размеры карты }
  map:array [0..52*52] of char; { карта }
  q:array [0..50*50] of integer; { очередь } 
  q1,q2:integer; { индекс начала и конца очереди }
  step:array [0..52*52] of integer; { информация о времени возгорания, -1 означает, что дом не горел }
  maxkol,maxr,maxc, { наилучший результат и координаты дома для поджога }
  curstep,newstep, { текущее время и время возгорания следующего дома }
  qpos0,qpos1,qpos2, { начальные позиции в очереди для предыдущего, текущего и нового времени возгорания }
  i,j,p,pn:integer; {вспомогательные переменные }

Первая часть программы – ввод данных. Двумерная карта города размером `(n+2)\ times\ (m+2)` хранится в одномерном массиве последовательно по строкам. Ячейка с координатами `(i,j)` в одномерном массиве имеет индекс `i*(m+2)+j`. Строки карты с номерами 0 и `n+1` и столбцы с номерами 0 и `m+1` заполняются символами '.'.

  readln(n,m);
  for j:=0 to m+1 do
    map[j]:='.';
  for i:=1 to n do
  begin
    map[i*(m+2)]:='.';
    for j:=1 to m do
      read(map[i*(m+2)+j]);
    map[i*(m+2)+m+1]:='.';
    readln;
  end;
  for j:=0 to m+1 do
    map[(n+1)*(m+2)+j]:='.';

Далее перебираем все варианты, какой дом будет подожжен первым, и выполняем поиск в ширину. При изменении времени возгорания смещаем позиции указателей qpos0, qpos1, qpos2 в очереди и проверяем на увеличение текущего максимума одновременно горящих домов.

  maxkol:=0;
  for i:=1 to n do
    for j:=1 to m do
    begin
      p:=i*(m+2)+j; { выбираем клетку (i,j) }
      if map[p]='#' then { если там есть дом }
      begin
        for pn:=0 to (n+2)*(m+2)-1 do { очищаем массив времени возгорания }
          step[pn]:=-1;
        step[p]:=0; { дом в клетке (i,j) загорается в момент 0 }
        q[0]:=p; { помещаем его в очередь }
        q1:=0;q2:=1;
        curstep:=0;
        qpos0:=0;
        qpos1:=0;
        qpos2:=0;
        while q1<q2 do { очередь не пуста }
        begin
          p:=q[q1];
          inc(q1);
          newstep:=step[p]+1; { новое время }
          if newstep>curstep then { время изменилось }
          begin
            qpos0:=qpos1; {  сдвигаем указатели }
            qpos1:=qpos2;
            qpos2:=q2;
            curstep:=newstep;
            if qpos2-qpos0>maxkol then { найден новый максимум }
            begin
              maxkol:=qpos2-qpos0; { запоминаем }
              maxr:=i;
              maxc:=j;
            end;
          end;
          fire(p+1); { поджигаем все соседние дома }
          fire(p-1);
          fire(p+m+1);
          fire(p+m+2);
          fire(p+m+3);
          fire(p-m-1);
          fire(p-m-2);
          fire(p-m-3);
        end;
      end;
    end;

Подпрограмма fire выглядит следующим образом:

procedure fire(p:integer);
begin
  if (map[p]='#') and (step[p]=-1) then { в позиции p есть дом, который еще не горел }
  begin
    step[p]:=newstep; { отмечаем время возгорания }
    q[q2]:=p; { добавляем дом в очередь }
    inc(q2);
  end;
end;

В завершающей части программ выводится найденный максимум и координаты дома.

  writeln(maxkol);
  writeln(maxr,' ',maxc);

Другим способом ускорения работы своей программы является выключение проверок на выход за границы массива и переполнение, включенных по умолчанию при компиляции – см. опции компилятора на странице Помощь. Для этого в начале программы нужно дописать комментарий:

{$R-} {$Q-} {$S-}

Следует отметить, что на первоначальных этапах разработки эти проверки являются достаточно важными и дают дополнительную информацию для исправления ошибок в программе. Ошибка времени исполнения (RT) часто сигнализирует о неправильно выбранном диапазоне для цикла или неправильно выбранном типе данных (integer вместо longint или int64). При выключении проверок ошибка типа RT превращается в WA или PE, которые обычно сигнализируют о нерассмотренном случае или неверной формуле.
Рекомендуется выключать проверки только при получении TL, и такое выключение сможет помочь только в случае, если реализованный алгоритм решения задачи требует существенно меньше `10^9` операций. Иначе нужно изменять алгоритм.