Каждый элемент квадратной матрицы размером NxN равен нулю, либо единице. найдите количество "островов", образованных единицами. Под "островом" понимается группа единиц (либо одна единица), со всех сторон окруженная нулями (или ...
Каждый элемент квадратной матрицы размером NxN равен нулю, либо единице. найдите количество "островов", образованных единицами. Под "островом" понимается группа единиц (либо одна единица), со всех сторон окруженная нулями (или краями матрицы). Единицы относятся к одному "острову", если из одной из них можно перейти к другой, "наступая" на единицы, расположенные в соседних клетках. Соседними являются клетки, граничащие по горизонтали или вертикали. Входные данные читаются из файла INPUT.TZT результат выводится в файл OUTPUT.TXT.
Гость
Ответ(ы) на вопрос:
ГостьПришлось написать рекурсивную процедуру. Надеюсь, это не вызовет вопросов.
Во вложениях даны тестовые файлы.
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.
Не нашли ответ?
Похожие вопросы