Каждый элемент квадратной матрицы размером 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.
193.125 в 10=1x10²+9x10¹+3x10⁰+1x10⁻¹+2x10⁻²+5x10⁻³ 193125 в 8=1x8⁵+9x8⁴+3x8³+1x8²+2x8¹+5x8⁰ 193125 в 16=1x16⁵+9x16⁴+3x16³+1x16²+2x16¹+5x16⁰ 1931.25 в 5=1x5³+9x5²+3x5¹+1x5⁰+2x5⁻¹+5x5⁻²
С точки зрения информатики наиболее важными представляются следующие общие качественные свойства: достоверность, полнота, точность, актуальность, полезность, ценность, своевременность, понятность, доступность, краткость и пр. Объективность информации