В матрице найти наибольший квадрат состоящий из единиц - 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.
- Инициализация матрицы случайными единицами и нулями.
- Поиск наибольшего квадрата, состоящего из единиц, начиная с верхнего левого угла.
- Проверка каждого элемента матрицы на равенство единице.
- Если элемент равен единице, то проверяется размер квадрата, начиная с этого элемента.
- Если размер квадрата больше текущего максимального, то обновляются координаты и размер максимального квадрата.
- Вывод сообщения о найденном максимальном квадрате и его координатах.