1

Тема: Максимальна площа прямокутника в матриці

Масив з нулів і одиниць. В ньому потрібно знайти площу найбільшого прямокутника, утвореного одиницями.

Мій код:

int _tmain(int argc, _TCHAR* argv[])
{
    const int WIDTH=4, HEIGHT=4;
    int C[WIDTH][HEIGHT],i,j;
    int Area=0, MaxArea=0;
    int Width=0, Height=0;
    srand(time(0));
    for (i=0; i < WIDTH; i++)
    {
        for (j=0; j < HEIGHT; j++)
        {
        C[i][j]=rand()%2;
        cout<<C[ i ][j]<<" ";
        }
        cout<<endl;
    }
    cout<<endl;
    for (i=0; i < WIDTH; i++)
    {
        for (j=0; j < HEIGHT; j++)
        {
            while (C[i][j]==1)
            {
                j++;
                Width++;
            }
            while (C[i][j]==1)
            {
                i++;
                Height++;
            }
                Area=Width*Height;
                if(MaxArea<Area)
                MaxArea=Area;
                Area=0;
                Width=0;
                Height=0;
        }
        }
    cout<<"Max area = "<<MaxArea<<endl;
    system("Pause");
    return 0;
}

у відповіді постійно 0, не можу зрозуміти в чому помилка.

2

Re: Максимальна площа прямокутника в матриці

Опишіть словами алгоритм, бо не можу зрозуміти, нащо в циклах while змінювати змінні циклів for.

3 Востаннє редагувалося Falko (17.11.2016 01:34:23)

Re: Максимальна площа прямокутника в матриці

Без цієї зміни не виводиться результат. Навіть не знаю як описати саме це місце в алгоритмі.

4

Re: Максимальна площа прямокутника в матриці

Falko написав:

Без цієї зміни не виводиться результат.

Можна подумати, з нею виводиться. Ідею, яка лежить за кодом, можете пояснити?

5

Re: Максимальна площа прямокутника в матриці

Перевіряємо кожен елемент почергово, поки йдуть одиниці - додаємо ширину і висоту відповідно. Таким чином знаходимо площу всіх прямокутників в матриці і порівнюємо з площею максимального

for (i=0; i < WIDTH; i++)
    {
        for (j=0; j < HEIGHT; j++)
        {
            while ( C[i][j]==1)
            {
                j++;
                Width++;
            }
            while ( C[i][j]==1)
            {
                i++;
                Height++;
            }
                Area=Width*Height;
                if(MaxArea<Area)
                MaxArea=Area;
                Area=0;
                Width=0;
                Height=0;
        }
        }

6 Востаннє редагувалося Falko (17.11.2016 01:52:42)

Re: Максимальна площа прямокутника в матриці

Можливо варто поставити границі типу:

   ki=i;
            kj=j; 
            while ( j<HEIGHT && C[ki][kj]==1)
            {
                kj++;
                Width++;
            }
            ki=i;
            kj=j;
            while (i < WIDTH && C[ki][kj]==1)
            {
                ki++;
                Height++;
            }

7

Re: Максимальна площа прямокутника в матриці

Перевіряємо кожен елемент почергово,

Фейл уже тут. Який елемент ви перевірите наступним, якщо C[0][0] == 1?

8 Востаннє редагувалося Falko (17.11.2016 01:57:31)

Re: Максимальна площа прямокутника в матриці

Наступний С[0][1], по ідеї :(
можливо є якісь ваші варіанти вирішення задачі?

9 Востаннє редагувалося quez (17.11.2016 02:00:18)

Re: Максимальна площа прямокутника в матриці

Falko написав:

Наступний С[0][1]

Тільки от j ви принаймні двічі інкрементували, тому C[0][1] це не може бути ніяк.

можливо є якісь ваші варіанти вирішення задачі?

Варіанти завжди є, просто їх час ще не настав. Спочатку треба придумати алгоритм, бо те, що ви написали своїми словами робить все що завгодно, тільки не те, про що йде мова в завданні

10

Re: Максимальна площа прямокутника в матриці

ось в доробленому коді в часткових випадках, знаходить правильну відповідь. другий цикл while я помістив перший.

int _tmain(int argc, _TCHAR* argv[])
{
    const int WIDTH=10, HEIGHT=10;
    int C[WIDTH][HEIGHT],i,j,ki,kj;
    int Area=0, MaxArea=0;
    int Width=0, Height=0;
    srand(time(0));
    for (i=0; i < WIDTH; i++)
    {
        for (j=0; j < HEIGHT; j++)
        {
        C[i][j]=rand()%2;
        cout<<C[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<endl;
    for (i=0; i < WIDTH; i++)
    {
        for (j=0; j < HEIGHT; j++)
        {
            ki=i;
            kj=j;
            while ( j<HEIGHT && C[ki][kj]==1)
            {
                kj++;
                Width++;

            ki=i;
            kj=j;
            while (i < WIDTH && C[ki][kj]==1)
            {
                ki++;
                Height++;
            }}
                Area=Width*Height;
                if(MaxArea<Area)
                MaxArea=Area;
                Area=0;
                Width=0;
                Height=0;
        }
        }
    cout<<"Max area = "<<MaxArea<<endl;
    system("Pause");
    return 0;

11

Re: Максимальна площа прямокутника в матриці

я намагався слідувати методу перебору

12

Re: Максимальна площа прямокутника в матриці

ой ні, щось пішло не так там, вже сам бачу... краще повернутися назад..

13 Востаннє редагувалося Falko (17.11.2016 09:38:05)

Re: Максимальна площа прямокутника в матриці

:(

14 Востаннє редагувалося quez (17.11.2016 02:39:59)

Re: Максимальна площа прямокутника в матриці

Форматуйте код, його ж неможливо читати!

Розкажіть детальніше про долю kj на цьому відрізку коду

            kj++;
            Width++;
 
            ki=i;
            kj=j;

Я розумію, що не нормально, коли програма працює, а я не розумію яким чином

Але ж вона не працює

15

Re: Максимальна площа прямокутника в матриці

потрібно, щоб в самому циклі while ми почергово перевіряли елементи, тому я ввів змінну kj i ki

for (i=0; i < WIDTH; i++)
        {
            for (j=0; j < HEIGHT; j++)
            {
            ki=i;
            kj=j;
            while ( kj<HEIGHT && C[ki][kj]==1)
            {
                max=0;
                while (ki < WIDTH && C[ki][kj]==1)
                {
                ki++ ;
                max++; 
                }
                if(kj-j==0)
                    Height=max;
                if(max<Height)
                    Height=max;
                Area=(kj-j+1)*Height;
                if(MaxArea<Area)
                    MaxArea=Area;
                ki=i;
                kj++; \\переходимо до наступного елемента в стовпчику;
            }
            }
        }

16

Re: Максимальна площа прямокутника в матриці

«Прямокутник, утворений одиницями» це отк:

0000000
0111110
0100010
0111110
0000000

чи отак

0000000
0111110
0111110
0111110
0000000

чи обидва варіанти підходять?

Це прямокутник, до якого причепився хвостик, чи це не прямокутник?

1111100
1111110
1111100
0000000

А оце?

1111110
0111110
0111110
0000000

Від відповідей на ці запитання залежить алгоритм, записаний людською мовою. Кодувати слід потім.

Подякували: koala1

17

Re: Максимальна площа прямокутника в матриці

1. Максимальні прямокутники 1х5 в 2 і 4 рядках.
2-4. Прямокутники 3х5
Прямокутник - пласка фігура, що має площу, тут питань немає. Але, дійсно, треба спершу сформулювати словами, що ми шукаємо.

18

Re: Максимальна площа прямокутника в матриці

Та воно наче й так (то коло і круг розрізняють, для інших фігур такого нема), але «побудувати прямокутник» означає провести чотири відповідних відрізки, заштриховування не вимагається.
І у комп. графіці є Rect (перший малюнок у мене, то один прямокутник, «намальований» відрізками з одиничкок), є FilledRect (другий малюнок).

Малюнки 3 і 4 точно підходять до «знайти площу найбільшого прямокутника, покритого одиницями» (тоді все, що виступає за межі прямокутника, просто ігнорується, а от прямокутник в координатах таких-то покритий і цього досить), а от щодо всього іншого потрібні уточнення, бо ті фігури прямокутниками не є.

Прихований текст

Так, я зануда.

19

Re: Максимальна площа прямокутника в матриці

це не рахується

0000000
0111110
0100010
0111110
0000000

я зробив дану задачу, варто залишати її тут чи нехай майбутнє покоління думає саме? :)

20

Re: Максимальна площа прямокутника в матриці

Та все ж виклади, бо цікаво про які прямокутники йшла мова ;)