Определить вписанный в решётку прямоугольник максимальной площади

@msk19 · Регистрация: 16.11.2015

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

На квадратном клетчатом листе бумаги 8x8 клеток заштрихована часть клеток (пример на рисунке). Определить вписанный в решётку прямоугольник максимальной площади, не содержащий заштрихованных клеток. В качестве ответа вывести площадь прямоугольника и координаты его двух противоположных вершин. (Предполагается, что прямоугольник с максимальной площадью один.)
Для приведенного примера координаты вершин (3,4) и (7,6), площадь 15 клеток.
Объясните по подробнее плиз алгоритм поиска этого прямоугольника

ФедосеевПавел · 12.12.2015, 20:30

Первое, что приходит на ум:
1. Принимаем максимум равным нулю.
2. Просматриваем матрицу по порядку слева-направо и сверху-вниз, пропуская заштрихованные клетки.
3. Когда находится белая клетка, начинаем исследовать:
3.1. Пытаемся расширить прямоугольник вправо на максимальное число клеток.
3.2. Пытаемся расширить прямоугольник вниз на максимальное число клеток.
3.3. Вычисляем площадь прямоугольника
3.4. Если площадь больше максимума, то запоминаем новое значение и координаты прямоугольника.
3.5. Уменьшаем правую границу на 1 клетку влево
3.6. переход к п.3.2.
3.7. Выполнять п.п.3.2-3.6 пока ширина больше 1 клетки.
4. Переход к п.2 - ищем следующую клетку.

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

@msk19 · 12.12.2015, 21:40 **[ТС]**

вроде понял
п.3.5 .Вы предлагаете уменьшать правую границу именно найденного не заштрихованного прямоугольника?
А если :
1. Принимаем максимум равным нулю.
2. Просматриваем матрицу по порядку слева-направо и сверху-вниз, пропуская заштрихованные клетки.
3. Когда находится белая клетка, начинаем исследовать:
3.1. Пытаемся расширить прямоугольник вправо на максимальное число клеток.
3.2. Пытаемся расширить прямоугольник вниз на максимальное число клеток.
3.3. Вычисляем площадь прямоугольника
3.4. Если площадь больше максимума, то запоминаем новое значение и координаты прямоугольника.
3.5. Переход к п.2.Находим все возможные прямоугольники и запоминаем максимальный
3.6. Уменьшаем правую границу первоначального квадрата 8х8 на 1 клетку влево ,чтоб получилось 8х7
3.6. Переход к п.2.
3.7. Выполнять п.п.3.2-3.6 пока ширина больше 1 клетки.
Получится???

ФедосеевПавел · 12.12.2015, 22:14

Думаю - нет.
То о чем я писал можно проиллюстрировать так. Здесь уже были просмотрены другие белые клетки, поэтому Smax уже не ноль. И вот найдена очередная белая клетка (3,4). Дальше на картинках

ФедосеевПавел · 12.12.2015, 22:24

Так несколько подробнее

@msk19 · 13.12.2015, 20:10 **[ТС]**

Сообщение от ФедосеевПавел

Думаю - нет

ясно
спасибо большое

Добавлено через 18 часов 28 минут
никак не получается записать пункты 3.1-3.2
Идея такая:
1.найти очередной белый квадратик
2.запомнить его начальную координату по горизонтали
3.начать наращивать прямоугольник вправо,пока не наткнусь на черный квадрат
3.5. запомнить длину этого прямоугольника и его конечную точку
4.увеличить координату по вертикали на 1 в начальной точке прямоугольника или в конечной, если там белый квадратик, тогда п.5
5.начать проверять есть ли черные квадраты на очередной строчке ,если нету тогда найти площадь,если есть закончить наращивание прямоугольника
Но когда начинаю писать программу,она на столько запутывается ,что ничего не получается
Добавлено через 2 часа 33 минуты

Pascal

var z:array[1..8,1..8] of integer=((0,0,1,0,1,0,0,0),
                                   (0,1,1,0,1,1,0,0),
                                   (1,1,1,0,0,0,0,1),
                                   (1,1,0,0,0,0,1,1),
                                   (0,0,0,0,0,0,0,1),
                                   (0,0,0,0,0,0,1,1),
                                   (0,0,1,0,0,0,0,0),
                                   (0,1,0,1,0,1,0,1));
mx,t,p,s,u,nc,r:integer;
procedure pc;
var q:integer;
begin            u:=0;   nc:=p;
for q:=p to 8 do
begin
if z[t,q]=0 then u:=u+1 else break;
  if p=8 then break;
    if u>1 then p:=p+1;
end;   end;
procedure y;
var q,h,y,y1,y2,y3,s1:integer;
begin
         y:=0;  y1:=0; y2:=0; y3:=0;
          if t<8 then
  for q:=t to 8 do  begin
  y1:=y1+1;
     for h:=nc to p do
     if z[q,h]<>0 then y:=1;
               if y=1 then break
                 else s1:=u*y1;
                end;
           if t>1 then
     for q:=t downto 1 do  begin
  y2:=y2+1;
        for h:=nc to p do
     if z[q,h]<>0 then y3:=1;
               if y3=1 then break
                 else s:=u*y2;
                end;
 
             if s1>s then s:=s1;
 end;
 
begin                t:=3;p:=4;
pc; 
  if u>=1 then y;
      write(s);
 
readln
end.

Находит площадь если задать координату пустого квадрата ,дальше не получается

ФедосеевПавел · 13.12.2015, 22:56

Попробуйте самостоятельно. У меня закончились выходные и до следующих я выпадаю из общественной жизни.

Для облегчения программирования и поиска ошибок воспользуйтесь форматтером кода JCF (он с прибабахами, но с ним лучше, чем без него).
А также, избавьтесь, по возможности, от глобальных переменных.
Давайте переменным осмысленные имена.
Не брезгуйте комментариями.

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

4.увеличить координату по вертикали на 1 в начальной точке прямоугольника или в конечной, если там белый квадратик, тогда п.5
5.начать проверять есть ли черные квадраты на очередной строчке ,если нету тогда найти площадь,если есть закончить наращивание прямоугольника

Это излишнее. Тут правильнее увеличить вертикальную координату на 1, проверить, что новая координата <=8, а потом проверить всю подстроку на отсутствие 1 (черных квадратов).

@msk19 · 13.12.2015, 23:44 **[ТС]**

решил) Правда по другому алгоритму,нужно взять координату одной левой верхней точки ,начиная с начала и перебирать для нее координаты всех правых нижних точек начиная с точки (8,8),до тех пор ,пока не найдется прямоугольник без единиц

Pascal

var z:array[1..8,1..8] of integer=((0,0,1,0,1,0,0,0),
                                   (0,1,1,0,1,1,0,0),
                                   (1,1,1,0,0,0,0,1),
                                   (1,1,0,0,0,0,1,1),
                                   (0,0,0,0,0,0,0,1),
                                   (0,0,0,0,0,0,1,1),
                                   (0,0,1,0,0,0,0,0),
                                   (0,1,0,1,0,1,0,1));
k:array[1..4] of integer;
mx,lv,l,pn,p,h,dl,s:integer;
function pr(l1,lv1,p1,pn1:integer):integer;
var y,p:integer;
begin               pr:=0;  h:=0; dl:=0 ;
 for y:=p1 downto l1 do begin
    h:=h+1; {высота прямоугольника}
    for p:=pn1 downto lv1 do  begin
     if h=1 then dl:=dl+1; {длина}
      if z[y,p]=1 then pr:=1;
      end; end;
end;
begin              mx:=0;
 for l:=1 to 8 do {координаты левой верхней точки}
  for lv:=1 to 8 do
   for p:=8 downto 1 do {координаты правой нижней}
    for pn:=8 downto 1 do
     if pr(l,lv,p,pn)=0 then  begin
        S:=h*dl;
         if S>mx then begin  mx:=s;
         k[1]:=l;k[2]:=lv;
         k[3]:=p;k[4]:=pn;
                          end;
         end;
         writeln(mx,'koord: ');
         writeln(k[1],'  ',k[2]);
         writeln(k[3],'  ',k[4]);
    readln
    end.

Определить вписанный в решётку прямоугольник максимальной площади

Решение

Решение

Решение

@msk19 39 / 2 / 3 Регистрация: 16.11.2015 Сообщений: 103
		1
	Определить вписанный в решётку прямоугольник максимальной площади 12.12.2015, 17:03. Показов 2666. Ответов 7 Метки нет (Все метки) На квадратном клетчатом листе бумаги 8x8 клеток заштрихована часть клеток (пример на рисунке). Определить вписанный в решётку прямоугольник максимальной площади, не содержащий заштрихованных клеток. В качестве ответа вывести площадь прямоугольника и координаты его двух противоположных вершин. (Предполагается, что прямоугольник с максимальной площадью один.) Для приведенного примера координаты вершин (3,4) и (7,6), площадь 15 клеток. Объясните по подробнее плиз алгоритм поиска этого прямоугольника Изображения 0

ФедосеевПавел Модератор 8477 / 4335 / 1643 Регистрация: 01.02.2015 Сообщений: 13,462 Записей в блоге: 8
	12.12.2015, 20:30	2
	Сообщение было отмечено msk19 как решение Решение Первое, что приходит на ум: 1. Принимаем максимум равным нулю. 2. Просматриваем матрицу по порядку слева-направо и сверху-вниз, пропуская заштрихованные клетки. 3. Когда находится белая клетка, начинаем исследовать: 3.1. Пытаемся расширить прямоугольник вправо на максимальное число клеток. 3.2. Пытаемся расширить прямоугольник вниз на максимальное число клеток. 3.3. Вычисляем площадь прямоугольника 3.4. Если площадь больше максимума, то запоминаем новое значение и координаты прямоугольника. 3.5. Уменьшаем правую границу на 1 клетку влево 3.6. переход к п.3.2. 3.7. Выполнять п.п.3.2-3.6 пока ширина больше 1 клетки. 4. Переход к п.2 - ищем следующую клетку. Ещё можно попробовать воспользоваться ситуацией - малый размер матрицы и кратность 8 (ассоциации с 8 бит). При помощи битовых операций AND и выделения маски прямоугольников, вычисления длин битовых последовательностей 1 и 0. Но это наверное даже сложнее. 1

@msk19 39 / 2 / 3 Регистрация: 16.11.2015 Сообщений: 103
	12.12.2015, 21:40 [ТС]	3
	вроде понял п.3.5 .Вы предлагаете уменьшать правую границу именно найденного не заштрихованного прямоугольника? А если : 1. Принимаем максимум равным нулю. 2. Просматриваем матрицу по порядку слева-направо и сверху-вниз, пропуская заштрихованные клетки. 3. Когда находится белая клетка, начинаем исследовать: 3.1. Пытаемся расширить прямоугольник вправо на максимальное число клеток. 3.2. Пытаемся расширить прямоугольник вниз на максимальное число клеток. 3.3. Вычисляем площадь прямоугольника 3.4. Если площадь больше максимума, то запоминаем новое значение и координаты прямоугольника. 3.5. Переход к п.2.Находим все возможные прямоугольники и запоминаем максимальный 3.6. Уменьшаем правую границу первоначального квадрата 8х8 на 1 клетку влево ,чтоб получилось 8х7 3.6. Переход к п.2. 3.7. Выполнять п.п.3.2-3.6 пока ширина больше 1 клетки. Получится??? 0

ФедосеевПавел Модератор 8477 / 4335 / 1643 Регистрация: 01.02.2015 Сообщений: 13,462 Записей в блоге: 8
	12.12.2015, 22:14	4
	Сообщение было отмечено msk19 как решение Решение Думаю - нет. То о чем я писал можно проиллюстрировать так. Здесь уже были просмотрены другие белые клетки, поэтому Smax уже не ноль. И вот найдена очередная белая клетка (3,4). Дальше на картинках Миниатюры 1

ФедосеевПавел Модератор 8477 / 4335 / 1643 Регистрация: 01.02.2015 Сообщений: 13,462 Записей в блоге: 8
	12.12.2015, 22:24	5
	Сообщение было отмечено msk19 как решение Решение Так несколько подробнее Миниатюры 1

ФедосеевПавел Модератор 8477 / 4335 / 1643 Регистрация: 01.02.2015 Сообщений: 13,462 Записей в блоге: 8
	13.12.2015, 22:56	7
	Попробуйте самостоятельно. У меня закончились выходные и до следующих я выпадаю из общественной жизни. Для облегчения программирования и поиска ошибок воспользуйтесь форматтером кода JCF (он с прибабахами, но с ним лучше, чем без него). А также, избавьтесь, по возможности, от глобальных переменных. Давайте переменным осмысленные имена. Не брезгуйте комментариями. Сообщение от msk19 4.увеличить координату по вертикали на 1 в начальной точке прямоугольника или в конечной, если там белый квадратик, тогда п.5 5.начать проверять есть ли черные квадраты на очередной строчке ,если нету тогда найти площадь,если есть закончить наращивание прямоугольника Это излишнее. Тут правильнее увеличить вертикальную координату на 1, проверить, что новая координата <=8, а потом проверить всю подстроку на отсутствие 1 (черных квадратов). 1

	13.12.2015, 23:44