Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Delphi программирование > Общие вопросы Delphi
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 10.05.2017, 16:12   #1
Armageddets
Форумчанин
 
Регистрация: 30.06.2012
Сообщений: 145
По умолчанию В матрице найти подматрицу с наибольшей площадью

Всем доброго времени суток, уважаемые эксперты. Нужно сделать следующее задание

Пусть имеется некоторая матрица , состоящая из строк и столбцов, каждый элемент которой является целым числом из множества.
Найти в заданной матрице максимальную по площади прямоугольную подматрицу, состоящую только из нулей или только из единиц.

Имеется три файла task1.txt, task2.txt и task3.txt, каждый из которых содержит описание одной матрицы в следующем формате.
<Число строк> <Число столбцов>
<Первая строка матриц>
<Вторая строка матрицы>

<Последняя строка матрицы>

Я сделал загрузку из файла данных такого вида:
3 3
000
011
011

Эти данные загружаю в мемо. Из него данные передаю в массив (mas).
А вот сам алгоритм поиска максимальной подматрицы с единицами или нулями пока не получается правильно.

Последний вариант, над которым работаю пробую сделать так. Например ищу единицы. Я в цикле пробегаю по всем ячейкам и ищу единицу. Как только она найдена - я начинаю с ее координат искать со смещением влево и вниз продолжение серии единиц. Но сам себя путаю в своем же алгоритме. Переделал алгоритм под цикл While и тут поиск идет не правильно конечно же. Посоветуйте как лучше изменить алгоритм или каким путем пойти?

Код:
  //znacheniya naydennoy matrici
  mX:=-1; //x координата левой верхней части подматрицы
  mY:=-1; //у координата левой верхней части подматрицы
  Mrx:=-1; //ширина подматрицы
  Mry:=-1; //высота подматрицы


//poisk edinichnih matric
  for i:=0 to XX-2 do
  for j:=0 to YY-2 do
  begin
    //ishem edinitsu
    if mas[i,j]=1 then
    begin
      //до каких границ продолжаем поиск подматрицы 
      xMax:=i;
      yMax:=j;
      while (yMax<=YY-1) do
      begin
      u:=true;
        for ii:=i to xMax do
        for jj:=j to yMax do
        if Mas[ii,jj]<>1 then u:=false;

        xnum:=xmax-ii+1;
        ynum:=ymax-jj+1;
        
        if u=True then
        begin
          //sravnivaem s posledney naydennoy matricey
          if Mrx*Mry<Xnum*Ynum then
          begin
          mX:=i;
          mY:=j;
          Mrx:=xnum;
          MrY:=ynum;
          end;
        end;

      Inc(xMax);
        if xMax>XX-1 then
        begin
        Inc(yMax);
        xmax:=i;
        end;
      end;

    end;
  end;
Armageddets вне форума Ответить с цитированием
Старый 10.05.2017, 16:44   #2
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,238
По умолчанию

посмотрите, может быть, найдёте то, что Вам нужно:

на форуме
МИННОЕ ПОЛЕ В Delphi

либо:
ссылка раз - Найти наибольший по площади прямоугольник из единиц в матрице

ссылка два - Найти подматрицу по условиям
Serge_Bliznykov вне форума Ответить с цитированием
Старый 11.05.2017, 00:16   #3
Armageddets
Форумчанин
 
Регистрация: 30.06.2012
Сообщений: 145
По умолчанию

Спасибо. Помогло.
Armageddets вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Найти макс. подматрицу из единиц максимального размера Kef1r Паскаль, Turbo Pascal, PascalABC.NET 2 04.02.2017 13:56
Найти треугольник с наибольшей площадью с вершинами в точках заданных координатами (подправить код) C++ GrShOot Помощь студентам 0 28.05.2013 01:47
Вывести страну с наибольшей площадью arefdiman Паскаль, Turbo Pascal, PascalABC.NET 0 06.05.2011 01:09
Найти в матрице квадратную подматрицу Apis Помощь студентам 3 26.04.2010 21:18
Определение параллелограмма с наибольшей площадью. Delphi. Absentik Помощь студентам 0 19.11.2009 17:15