3. Поиск в глубину

Разбор задачи 1309. Считая облака

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

var map:array[1..200]of string; { снимок неба }
    k,i,j,n,m:integer;
begin
  { ввод данных }
  readln(n,m);
  for i:=1 to n do 
    readln(map[i]);
  for i:=1 to n do { сканируем снимок }
    for j := 1 to m do
      if map[i][j]='#' then { нашли незакрашенную область }
      begin
        recolor(i,j); { перекрашиваем }
        inc(k); { увеличиваем счетчик найденных областей }
      end;
  writeln(k);
end.

Алгоритм закраски реализуется как рекурсивная подпрограмма.

procedure recolor(i,j:integer);
begin
  if (i<1)or (i>n) or  (j<1) or (j>m) { вышли за границу снимка }
     or (map[i][j]<>'#') then { или уже перекрашена или пуста }
    exit;
  map[i][j]:='+'; { отмечаем (i,j) клетку как перекрашенную }
  recolor(i+1,j); { пытаемся перекрасить её 4 соседей }
  recolor(i-1,j);
  recolor(i,j+1);
  recolor(i,j-1);
end;