Question

Каждый элемент квадратной матрицы размером NxN равен нулю, либо единице. найдите количество "островов", образованных единицами. Под "островом" понимается группа единиц (либо одна единица), со всех сторон окруженная нулями (или краями матрицы). Единицы относятся к одному "острову", если из одной из них можно перейти к другой, "наступая" на единицы, расположенные в соседних клетках. Соседними являются клетки, граничащие по горизонтали или вертикали. Входные данные читаются из файла INPUT.TZT результат выводится в файл OUTPUT.TXT.

Answer 1

Пришлось написать рекурсивную процедуру. Надеюсь, это не вызовет вопросов.
Во вложениях даны тестовые файлы.

const
  n1 = 20;

type
  r5 = record
    value: byte; {Значение элемента}
    right: boolean; {Есть ли единица справа?}
    down: boolean; {Есть ли единица ниже?}
    left: boolean; {Есть ли единица слева?}
    viewed: boolean {Элемент просмотрен?}
  end;

var
  n, i, j, k: integer;
  m: array[1..n1, 1..n1] of r5;
  fin, fout: Text;

procedure Mark(i: integer; j: integer);
{рекурсивная процедура, отыскивающая весь островок и помечающая его}
begin
  if not m[i, j].viewed then
  begin
    m[i, j].viewed := true;
    if m[i, j].right then Mark(i, j + 1);
    if m[i, j].down then Mark(i + 1, j);
    if m[i, j].left then Mark(i, j - 1)
  end
end;

begin
  Assign(fin, 'Input.txt');
  Reset(fin);
  {Инициализация из файла}
  Readln(fin, n);
  for i := 1 to n do
    for j := 1 to n do
      Read(fin, m[i, j].value);
  Close(fin);
  {Определение соседей}
  for i := 1 to n do
    for j := 1 to n do
    begin
      if m[i, j].value = 1 then begin
        if j < n then m[i, j].right := (m[i, j + 1].value = 1) else m[i, j].right := false;
        if i < n then m[i, j].down := (m[i + 1, j].value = 1) else m[i, j].down := false;
        if j > 1 then m[i, j].left := (m[i, j - 1].value = 1) else m[i, j].left := false
      end;
      m[i, j].viewed := false
    end;
  {Подсчет "островков"}
  k := 0;
  for i := 1 to n do
    for j := 1 to n do
    begin
      with m[i, j] do
      begin
        if (m[i, j].value = 1) and (not m[i, j].viewed) then begin
          k := k + 1;
          Mark(i, j)
        end
      end
    end;
  Assign(fout, 'Output.txt');
  Rewrite(fout);
  Writeln(fout, k);
  Close(fout)
end.

1442642b3972a396af45231272efa0e9.txt

c59b0f1454427bfdc16418f8f336d472.txt

Answer 2

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

Answer 3

Если не устраивает Паскаль, можно и на другом языке написать, только в Паскале алгоритм "прозрачнее".