Олимпиадная задача на графы "Острова"

[к списку задач]

Каждый элемент квадратной матрицы размеренности N x N равен нулю, либо единице. Найдите количество «островов», образованных единицами. Под «островом» понимается группа единиц (либо одна единица), со всех сторон окруженная нулями (или краями матрицы). Единицы относятся к одному «острову», если из одной из них можно перейти к другой «наступая» на единицы, расположенные в соседних клетках. Соседними являются клетки, граничащие по горизонтали или вертикали.

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

Входные данные

В первой строке файла INPUT.TXT записано натуральное число N не больше 100 - размер квадратной матрицы. В следующих N строках задаются элементы матрицы через пробел.

Выходные данные

В файл OUTPUT.TXT выведите единственное число - количество островов.

Пример

Решение задачи

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

Поскольку тест задачи не слишком мал, стоит написать процедуру уничтожения островов, назовем ее "count". Чтобы во время выполнения процедуру не "выскочить" за пределы массива, сделаем его не размером N x N, а размеров N+2 x N+2, это даст  нам возможность окружить искомый массив размером N x N  нулями.

const
  m = 102;
var
  a:array [1..m, 1..m] of integer;
  i,j,n,res: integer;
  input,output: text;
procedure count(i,j: integer);
  begin
    if a[i,j] <> 1 then
      exit;
    a[i,j] := 0;
    count(i + 1, j);
    count(i - 1, j);
    count(i, j + 1);
    count(i, j - 1);
  end;
begin
  res:= 0;
  assign(input,'input.txt');
  reset(input);
  assign(output,'output.txt');
  rewrite(output);
  read(input, n);
  {Заполняем массив нулями}
  for i:= 1 to n+2 do
    for j:=1 to n+2 do
      a[i,j]:=0;
  {Считываем матрицу из файла}
  for i:= 2 to n+1 do
    for j:=2 to n+1 do
      read(input,a[i,j]);
  {Обходим матрицу в поиске островов}
  for i := 2 to n+1 do
    for j := 2 to n+1 do
      if a[i,j] = 1 then
        begin
          inc(res);
          count(i,j);
        end;
  write(output,res);
  close(input);
  close(output);
end.

[к списку задач]