Массив: Найти для строительства дома квадрат максимальной площади, свободный от деревьев.

@odmenTop · Регистрация: 18.03.2017

Author24 — интернет-сервис помощи студентам

Есть матрица 25x25, заполнена рандомно числами 0 и 1.
0 - пустой участок
1 - заполнен деревьями.
Найти для строительства дома квадрат максимальной площади, свободный от деревьев.
Помогите составить алгоритм поиска пустых участков(число 0).

@Matan! · 21.02.2018, 12:52

Сообщение от odmenTop

Помогите составить алгоритм поиска пустых участков(число 0).

От левого верхнего угла матрицы до правого нижнего
Найти 0
Если найден, то S(изначально = 0) = S + 1.

@AHBAR · 22.02.2018, 08:59

Сообщение от Matan!

От левого верхнего угла матрицы до правого нижнего
Найти 0
Если найден, то S(изначально = 0) = S + 1.

не все так просто, думаю тут нужно найти именно квадрат, а не тупо площадь пустых мест

@Puporev · 22.02.2018, 13:40

Можно найти таким хитрым способом. Алгоритм писка максимального квадрата из единиц позаимствовал на одном из форумов у товарищей Yuri Negometyanov и rdorn

Delphi
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
program Project2;
 
{$APPTYPE CONSOLE}
//**********************/questions/485486/ДП-Наибольшая-квадратная-подматрица-из-единиц
uses
  SysUtils,
  Math,
  Windows;
const n=25;
var a:array[0..n,0..n] of integer;
    i,j,mx:integer;
begin
SetConsoleCP(1251);
SetConsoleOutPutCp(1251);
randomize;
//заполним нулевые строку и столбец нолями
for i:=0 to n do
 begin
  a[0,i]:=0;
  a[i,0]:=0;
 end;
//заполним матрицу случайно 0 и 1
for i:=1 to n do
 begin
  for j:=1 to n do
   begin
    a[i,j]:=random(2);
    write(a[i,j]:2);
   end;
  writeln;
 end;
//заменим 0 на 1 и наоборот
for i:=1 to n do
for j:=1 to n do
a[i,j]:=abs(a[i,j]-1);
//будем искать макс. квадрат из 1
for i:=1 to n do
for j:=1 to n do
if a[i,j]<>0 then //если в клетке не 0
//выбираем минимальный из элементов слева и сверху
//и +1, если 1, то не изменится, иначе увеличится
a[i,j]:=min(min(a[i-1,j-1],a[i,j-1]),a[i-1,j])+1;
mx:=a[1,1];
for i:=1 to n do
for j:=1 to n do
if a[i,j]>mx then mx:=a[i,j];
write('Квадрат максимальной площади из нолей = ',mx,'*',mx);
readln
end.

Новые блоги и статьи Все статьи Все блоги /
Реализация операторов Kubernetes Mr. Docker 16.05.2025 Концепция операторов Kubernetes зародилась в недрах компании CoreOS (позже купленной Red Hat), когда команда инженеров искала способ автоматизировать управление распределёнными базами данных в. . .	Отражение в C# и динамическое управление типами stackOverflow 16.05.2025 Reflection API в . NET — это набор классов и интерфейсов в пространстве имён System. Reflection, который позволяет исследовать и манипулировать типами, методами, свойствами и другими элементами. . .	Настройка гиперпараметров с помощью Grid Search и Random Search в Python AI_Generated 15.05.2025 В машинном обучении существует фундаментальное разделение между параметрами и гиперпараметрами моделей. Если параметры – это те величины, которые алгоритм "изучает" непосредственно из данных (веса. . .	Сериализация и десериализация данных на Python py-thonny 15.05.2025 Сериализация — это своего рода "замораживание" объектов. Вы берёте живой, динамический объект из памяти и превращаете его в статичную строку или поток байтов. А десериализация выполняет обратный. . .	Чем асинхронная логика (схемотехника) лучше тактируемой, как я думаю, что помимо энергоэффективности - ещё и безопасность. Hrethgir 14.05.2025 Помимо огромного плюса в энергоэффективности, асинхронная логика - тотальный контроль над каждым совершённым тактом, а значит - безусловная безопасность, где безконтрольно не совершится ни одного. . .
Многопоточные приложения на C++ bytestream 14.05.2025 C++ всегда был языком, тесно работающим с железом, и потому особеннно эффективным для многопоточного программирования. Стандарт C++11 произвёл революцию, добавив в язык нативную поддержку потоков,. . .	Stack, Queue и Hashtable в C# UnmanagedCoder 14.05.2025 Каждый опытный разработчик наверняка сталкивался с ситуацией, когда невинный на первый взгляд List<T> превращался в узкое горлышко всего приложения. Причина проста: универсальность – это прекрасно,. . .	Как использовать OAuth2 со Spring Security в Java Javaican 14.05.2025 Протокол OAuth2 часто путают с механизмами аутентификации, хотя по сути это протокол авторизации. Представьте, что вместо передачи ключей от всего дома вашему другу, который пришёл полить цветы, вы. . .	Анализ текста на Python с NLTK и Spacy AI_Generated 14.05.2025 NLTK, старожил в мире обработки естественного языка на Python, содержит богатейшую коллекцию алгоритмов и готовых моделей. Эта библиотека отлично подходит для образовательных целей и. . .	Реализация DI в PHP Jason-Webb 13.05.2025 Когда я начинал писать свой первый крупный PHP-проект, моя архитектура напоминала запутаный клубок спагетти. Классы создавали другие классы внутри себя, зависимости жостко прописывались в коде, а о. . .

@odmenTop 0 / 0 / 0 Регистрация: 18.03.2017 Сообщений: 5

	Массив: Найти для строительства дома квадрат максимальной площади, свободный от деревьев. 21.02.2018, 09:56. Показов 842. Ответов 3 Метки нет (Все метки) Есть матрица 25x25, заполнена рандомно числами 0 и 1. 0 - пустой участок 1 - заполнен деревьями. Найти для строительства дома квадрат максимальной площади, свободный от деревьев. Помогите составить алгоритм поиска пустых участков(число 0). 0

Опции темы