Алгоритм поиска прямоугольников в матрице

@ChioraYaz · Регистрация: 29.03.2018

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

Суть задания: найти площадь наибольшего прямоугольника, стороны которого состоят из 'О'.

Что у меня есть сейчас: алгоритм через раз находит максимальный прямоугольник и для удобства выделяет его, после чего становится заметно, что иногда алгоритм не справляется.

Пожалуйста, укажите на ошибку в алгоритме.

Pascal
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
{1. Рисунок представляет собой прямоугольную матрицу, каждый пиксель которой может быть черным или белым.
Найти площадь максимального субпрямоугольника, у которого все стороны черные.
Если решать в «лоб», то трудоемкость равна O(N^4).}
 
 
begin
  var i, j, t, a, b :integer;//Для цикла
  var K: array[1..150,1..150] of char;
  var vi, ni, lj, pj :integer;//Края
  var S, Smax :integer;//Площадь
  var dlina, shirina, norm :integer;
  var mvi, mni, mlj, mpj :integer;//Края максимального субпрямоугольника
    
  write('Размерность: ',#10);
  write('строки: ');readln(a);
  write('столбцы: ');readln(b);
  
  Smax:=1; dlina:=1; Shirina:=1;
  
  //Заполнение и вывод
  writeln(#10, 'Матрица:');
  for i:=1 to a do begin
    write('| ');
    for j:=1 to b do begin
      
      t:=random(10);
      if (t<5) then K[i,j]:='.' else K[i,j]:='O'; //Для удобства 'О' - чёрные, '.' - белые
      write(K[i,j], ' ');
      
    end;
    writeln('|');
  end;
  
  
  
  
  //Проход
  for i:=1 to a do begin
    for j:=1 to b do begin
      
      //Начало
      if (K[i,j]='O') then begin
        
        norm:=1; //Рубильник перехода к следующей итерации, если длина/ширина равна единице или прямоугольник не сомкнулся
        
        //Лево вверху
        vi:=i;
        lj:=j;
        
        
        //ВПРАВО--------------------------------------------------
        for t:=lj to b do begin
          if (K[vi,t]='.') then begin
            pj:=t-1;
            if lj=pj then norm:=0;
            break;
          end
          else begin
            if t=b then begin
              pj:=t;
              if lj=pj then norm:=0;
              break;
            end;
          end;
        end;
        
        if norm=0 then continue;        
        
        //ВНИЗ--------------------------------------------------
        for t:=vi to a do begin
          if (K[t,pj]='.') then begin
            ni:=t-1;
            if vi=ni then norm:=0;
            break;
          end
          else begin
            if t=a then begin
              ni:=t;
              if vi=ni then norm:=0;
              break;
            end;
          end;
        end;
        
        if norm=0 then continue;
        
        //ВЛЕВО--------------------------------------------------
        for t:=pj downto lj do begin
          if (K[ni,t]='.') then begin
            norm:=0;
            break;
          end
          else begin
            if t=lj then begin
              break;
            end;
          end;
        end;
        
        if norm=0 then continue;
        
        //ВВЕРХ--------------------------------------------------
        for t:=ni downto vi do begin
          if (K[t,lj]='.') then begin
            norm:=0;
            break;
          end;
        end;
        
        //ПЛОЩАДЬ
        if norm=1 then begin
          dlina:=pj-lj+1;
          shirina:=ni-vi+1;
          {writeln('D: ', dlina, '    S: ', shirina);
          writeln('pj: ', pj, '   lj: ', lj);
          writeln('ni: ', ni, '   vi: ', vi);}
          S:=dlina*shirina;
          
          if (S > Smax) then begin //Сравнение с максимальным
            Smax:=S;
          
            //Внесение новых максимальных границ
            mvi:=vi;
            mni:=ni;
            mlj:=lj;
            mpj:=pj;
          end;
        end;
        
      end;
      
    end;
  end;
   
  write(#10, #10, #10, 'Итог: ', Smax,#10);
  
  
  //Доп. вывод
  writeln(#10, 'Доп. вывод:');
  for i:=1 to a do begin
    write('| ');
    for j:=1 to b do begin
      write(K[i,j], ' ');
    end;
    writeln('|');
  end;
  
  //Покраска максимального субпрямоугольника
  if Smax>1 then begin
  
    for i:=mvi to mni do begin
      K[i,mlj] := 'Ж';
    end;
    for i:=mvi to mni do begin
      K[i,mpj] := 'Ж';
    end;
    for j:=mlj to mpj do begin
      K[mvi,j] := 'Ж';
    end;
    for j:=mlj to mpj do begin
      K[mni,j] := 'Ж';
    end;
   
    //Вывод с субпрямоугольником
    writeln(#10, 'Субпрямоугольник:');
    for i:=1 to a do begin
      write('| ');
      for j:=1 to b do begin
        write(K[i,j], ' ');
      end;
      writeln('|');
    end;
  
  end
  else write(#10, 'Показывать нечего.');
  
end.

Алгоритм поиска прямоугольников в матрице

@vrvrvrvr1234 · 01.04.2022, 19:40

Не очень хочу разбираться с вашим алгоритмом

. Написал свой(рабочий), но работает не быстро...

Pascal
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
begin
  var mx: array [,] of byte;
  var c:integer;
  var (max1,max2):=((0,0),(0,0));
  var mrx,mcx: array of (integer,integer);
  SetLength(mx,readlninteger('Ряды: '),readlninteger('Столбцы: '));
  for var i:=0 to mx.GetLength(1)-1 do
    for var j:=0 to mx.GetLength(0)-1 do
      begin
      mx[j,i]:=random(0,1);
      if mx[j,i]=0 then c+=1;
      end;
  Setlength(mrx,c);
  Setlength(mcx,c);
  c:=0;
 for var i:=0 to mx.GetLength(1)-1 do
    for var j:=0 to mx.GetLength(0)-1 do
      if mx[j,i]=0 then begin mrx[c]:=(j,i); c+=1; end;
 c:=0;
 for var j:=0 to mx.GetLength(0)-1 do
    for var i:=0 to mx.GetLength(1)-1 do
      if mx[j,i]=0 then begin mcx[c]:=(j,i); c+=1; end;
 c:=0;
 foreach var i in mcx do
   foreach var j in mcx do
     if (i[1]<=j[1]) and (i[0]<=j[0]) and (mcx.IndexOf((i[0],j[1]))<>-1) and (mcx.IndexOf((j[0],i[1]))<>-1) then
       if (mcx.IndexOf(i)-mcx.IndexOf((i[0],j[1]))=i[1]-j[1]) and (mcx.IndexOf((j[0],i[1]))-mcx.IndexOf(j)=i[1]-j[1]) and (mrx.IndexOf(i)-mrx.IndexOf((j[0],i[1]))=i[0]-j[0]) and (mrx.IndexOf((i[0],j[1]))-mrx.IndexOf(j)=i[0]-j[0]) then
         if (j[0]-i[0]+1)*(j[1]-i[1]+1)>c then begin
            c:=(j[0]-i[0]+1)*(j[1]-i[1]+1);
            max1:=i;
            max2:=j;
       end;
 for var i:=0 to mx.GetLength(0)-1 do println(mx.Row(i));
 println(max1,max2);
 print(c);
end.

Матрица начинается с координат 0 0. Выводится сама матрица, а затем углы искомого прямоугольника(верхний левый/правый нижний, сначала ряд, потом столбец). В конце выводится площадь.

Добавлено через 9 минут
Забыл сказать.. Границы прямоугольника из символа 0

@ChioraYaz · 05.04.2022, 14:27 **[ТС]**

Поскольку на ошибку мне не указали, я переделал другим способом, который работает.
Может, кому-нибудь пригодится.

Pascal
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
{1. Рисунок представляет собой прямоугольную матрицу, каждый пиксель которой может быть черным или белым.
Найти площадь максимального субпрямоугольника, у которого все стороны черные.
Если решать в «лоб», то трудоемкость равна O(N^4).}
 
 
  var K: array[1..300,1..300] of char;
 
 
function Proverka(i,j,p,q:integer) :integer; // Проверка на замкнутость полученного прямоугольника
begin
  
  var c :integer;
  
  //Верхняя сторона
  for c:=j to q do begin
    if K[i,c]='.' then begin
      Proverka:=0;
      Exit;
    end;
  end;
  
  //Левая сторона
  for c:=i to p do begin
    if K[c,j]='.' then begin
      Proverka:=0;
      Exit;
    end;
  end;
  
  //Нижняя сторона
  for c:=j to q do begin
    if K[p,c]='.' then begin
      Proverka:=0;
      Exit;
    end;
  end;
  
  //Правая сторона
  for c:=i to p do begin
    if K[c,q]='.' then begin
      Proverka:=0;
      Exit;
    end;
  end;
  
  Proverka:=1;  
  
end;
 
 
 
 
begin
  var i, j, p, q, t, t1, t2, a, b :integer;//Для цикла
  var vi, ni, lj, pj :integer;//Края углов
  var S, Smax :integer;//Площадь
  var dlina, shirina, norm, ap :integer;
  var mvi, mni, mlj, mpj :integer;//Края максимального субпрямоугольника
    
  write('Размерность: ',#10);
  write('строки: ');readln(a);
  write('столбцы: ');readln(b);
  
  Smax:=1; dlina:=1; shirina:=1;
  
  //Заполнение и вывод
  writeln(#10, 'Матрица:');
  for i:=1 to a do begin
    write('| ');
    for j:=1 to b do begin
      
      t:=random(10);
      if (t<5) then K[i,j]:='.' else K[i,j]:='O'; // 'О' - чёрные, '.' - белые
      write(K[i,j], ' ');
      
    end;
    writeln('|');
  end;
  
  t1:=milliseconds;
  
  //Проход с помощью координат вершин прямоугольника
  for i:=1 to a-1 do begin
    for j:=1 to b-1 do begin
      for p:=i+1 to a do begin
        for q:=j+1 to b do begin
          if (Proverka(i,j,p,q)=1) then begin
            
            dlina:=q-j+1;
            shirina:=p-i+1;
            S:=dlina*shirina;
            
            if (S>Smax) then begin
              
              Smax:=S;
              mvi:=i;
              mni:=p;
              mlj:=j;
              mpj:=q;
              
            end;
            
          end;
        end;
      end;
    end;
  end;
  
  t2:=milliseconds;
   
  writeln(#10, #10, #10, 'Максимальная площадь: ', Smax);
  writeln('Время: ', t2-t1, ' миллисекунд');
  
  
  
  //Доп. вывод
  {writeln(#10, 'Доп. вывод:');
  for i:=1 to a do begin
    write('| ');
    for j:=1 to b do begin
      write(K[i,j], ' ');
    end;
    writeln('|');
  end;}
  
  //Покраска максимального субпрямоугольника
  if Smax>1 then begin
  
    for i:=mvi to mni do begin
      K[i,mlj] := 'Ж';
    end;
    for i:=mvi to mni do begin
      K[i,mpj] := 'Ж';
    end;
    for j:=mlj to mpj do begin
      K[mvi,j] := 'Ж';
    end;
    for j:=mlj to mpj do begin
      K[mni,j] := 'Ж';
    end;
   
    //Вывод с субпрямоугольником
    writeln(#10, 'Субпрямоугольник:');
    for i:=1 to a do begin
      write('| ');
      for j:=1 to b do begin
        write(K[i,j], ' ');
      end;
      writeln('|');
    end;
  
  end
  else write(#10, 'Показывать нечего.');
  
end.
 
 
{for i:=1 to n-1 do
  for j:=1 to m-1 do
    for p:=i to n do
      for q:=j to m do
        Proverka(i,j,p,k)}

Новые блоги и статьи Все статьи Все блоги /
делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .
Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .