О задачах на клеточной карте - 2

Обходы в ширину, глубину и с выходом по флагу.

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

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

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

1 1 0 1 1

1 0 1 1 0

0 0 0 1 1

0 0 0 1 0

1 1 0 0 0

Одна область выделена красным, вторая синим, а третья – зеленым цветом.

А теперь рассмотрим один из способов решения нашей задачи. Назовем его обход с выходом по флагу.

Суть его в следующем: Перемещаемся по матрице, пока не встретим первую единицу. После этого увеличиваем счетчик количества областей на 1, а единицу превращаем в двойку. После этого сбрасываем флаг и начинаем проходить по матрице до тех пор, пока после завершения прохода флаг не останется сброшенным. В процессе прохода по матрице если встречаем единичный элемент, соседствующий с элементом равным двойке (справа, слева, сверху или снизу), то мы записываем в этот элемент двойку и устанавливаем флаг.

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

Задача 2.
Подсчитать площади всех островов.
Отличие: первый остров нумеруем 2, второй 3, ...

Const        {0 - море, 1 - острова}
 POLE1 : array[1..10,1..10] of INTEGER=
((1,1,0,1,0,0,1,0,0,0),
 (0,1,1,1,0,1,1,0,1,1),
 (1,1,0,1,1,1,0,0,1,0),
 (0,0,0,1,0,1,1,0,1,1),
 (1,1,1,1,1,1,0,0,0,1),
 (0,0,0,0,0,0,0,1,1,1),
 (0,1,0,1,0,1,0,0,0,0),
 (0,0,0,0,0,1,1,1,1,1),
 (0,1,0,1,0,1,0,1,0,1),
 (0,0,0,0,0,1,1,1,1,1));
Var
 POLE : array[0..11,0..11] of integer;  {вокруг карты каемка - море}
 I, J, k,S : INTEGER;
 I1, J1, FLAG : INTEGER;

Begin
FOR I:=1 TO 10 DO
  FOR J:=1 TO 10 DO
    POLE[I,J]:=POLE1[i,j];  {считывание данных из константы}

k:=0;
FOR I:=1 TO 10 do
  FOR J:=1 TO 10 do
    IF POLE[I,J]=1 THEN    
      begin
       k:=k+1;
       POLE[I,J]:=k;
       REPEAT
        FLAG:=0;
          FOR I1:=1 TO 10 do
           FOR J1:=1 TO 10 do
             IF POLE[I1,J1]=k THEN begin
               IF POLE[I1-1,J1]=1 THEN begin POLE[I1-1,J1]:=k; FLAG:=1 end;
               IF POLE[I1+1,J1]=1 THEN begin POLE[I1+1,J1]:=k; FLAG:=1 end;
               IF POLE[I1,J1-1]=1 THEN begin POLE[I1,J1-1]:=k; FLAG:=1 end;
               IF POLE[I1,J1+1]=1 THEN begin POLE[I1,J1+1]:=k; FLAG:=1 end;
             end; {IF}
       UNTIL FLAG=0;
      end; {if}
for i1:=2 to k do begin    {подсчет площадей}
  S:=0;
  FOR I:=1 TO 10 DO
    FOR J:=1 TO 10 DO
      if POLE[i,j]=i1 then s:=S+1;;
  writeln('площадь ',i1-1,'-го острова ',S);
  end;
End.

В данной бинарной матрице программа находит 7 изолированных областей.

Данный способ является одним из худших вариантов и по быстродействию (приходится многократно проходить по всей матрице) и по объему программного кода. Правда разновидность данного алгоритма, называемого «волновым алгоритмом Ли» (о котором мы говорили в прошлый раз) позволяет находить кратчайшие пути между элементами массива. Используется, в частности, для поиска кратчайшего выхода из лабиринта или трассировки печатных плат. Так, в волновом алгорите Ли все соседние с двойкой единицы превращаются не в двойки а в тройки, затем все соседние с тройками единицы превращаются в четверки и так далее. А кратчайший путь находится обратным ходом от больших чисел к двойке.