В матрице найти наибольший квадрат состоящий из единиц - PascalABC.NET
Формулировка задачи:
Задание: В матрице найти наибольший квадрат состоящий из едениц. Сама матрица состоит из 1 и 0. Помогите пожалуйста
Решение задачи: «В матрице найти наибольший квадрат состоящий из единиц»
textual
Листинг программы
begin var N := ReadLnInteger('N ='); var A : array [,] of Integer; SetLength(A, N, N); N -= 1; Randomize; for var Row := 0 to N do begin for var Col := 0 to N do begin A[Row,Col] := Random(0,2) = 0 ? 0 : 1; Write(A[Row,Col]:2); end; WriteLn; end; /// Координаты и размер квадрата var maxRow := 0; var maxCol := 0; var maxVal := 0; /// Для каждой единички for var Row := 0 to N do for var Col := 0 to N do if A[Row,Col] = 1 then begin /// Найдём размер квадрата var Quare := True; var qSize := 0; repeat qSize += 1; Quare := (Row+qSize < N) and (Col+qSize < N); if Quare then begin /// Сканируем квадрат /// (Не оптимально. Можно было бы сканировать только правую и нижнюю сторону ;-) for var dRow := Row to Row + qSize do for var dCol := Col to Col + qSize do Quare := Quare and (A[dRow,dCol] = 1); end; until Not Quare; /// Запомним наибольший if qSize > maxVal then begin maxRow := Row; maxCol := Col; maxVal := qSize; end; end; WriteLn('The max square = ', maxVal); WriteLn('Left-top = ', maxRow+1, 'x', maxCol+1); end.
Объяснение кода листинга программы
- Ввод размера матрицы N.
- Инициализация матрицы случайными единицами и нулями.
- Поиск наибольшего квадрата, состоящего из единиц, начиная с верхнего левого угла.
- Проверка каждого элемента матрицы на равенство единице.
- Если элемент равен единице, то проверяется размер квадрата, начиная с этого элемента.
- Если размер квадрата больше текущего максимального, то обновляются координаты и размер максимального квадрата.
- Вывод сообщения о найденном максимальном квадрате и его координатах.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д