Wyszukiwanie największego kwadratu

0

Witam, szukam sposobu na wyszukanie największego kwadratu w tablicy 2wymiarowej. Dajmy na to, że mamy taką tablicę:

1 5 9 1 4
3 1 1 4 1
1 1 1 1 6
1 1 1 7 1
1 1 1 1 1
2 5 1 6 1

Chodzi o to, aby znaleźć największy kwadrat jedynek. Ma ktoś jakiś pomysł jak powinien wyglądać algorytm? Albo wie gdzie można znaleźć jakieś informacje na ten temat?

0

ale ten problem jest prosty, a nie nietuzinkowy. Chodzisz po wszystkich elementach macierzy jeśli trafisz na jedynkę to sprawdzasz, jak duży kwadrat zaczepiony prawym górnym rogiem upchniesz w to miejsce, zapamiętujesz miejsce o największym kwadracie i koniec. Nic tylko siąść i pisać.

0

Można jaśniej? Męczę się z tym strasznie :/

0

Pomoże ktoś?

0

Najpierw determinujesz rozmiary największego możliwego kwadratu w tej tablicy. Np. w tablicy o wymiarze 6x5, taki możliwy kwadrat ma wymiary 5x5. Następnie zaczynasz sprawdzanie kwadratów w tej tablicy o tymże rozmiarze. Takich w w/w tablicy będzie 4. Szukasz tylko i wyłącznie jedynek w takiej podtablicy. Jak znajdziesz zero w takiej podtablicy, to nie szukasz dalej, tylko bierzesz kolejną podtablicę do sprawdzenia. Jak nie znajdziesz takiej podtablicy 5x5, to znaczy, że możliwe, że kwadrat taki będzie miał wymiary 4x4, takich jest już 6. I tak w kółko :)

0

pomyliłem się w 1 miejscu:

#include <iostream>

short SzukajKw(short tab[][7], int x, int y, int m);
short Szukaj(short tab[][7], int a, int b);

int main()
{
    using namespace std;

    short tablica[8][7] =
    {{1,1,1,2,3,4,5},
     {2,3,1,1,1,2,3},
     {2,1,1,1,1,1,3},
     {2,1,1,1,1,2,3},
     {2,1,1,1,1,2,3},
     {2,1,1,1,1,2,3},
     {2,3,1,1,1,2,3},
     {2,3,1,1,1,2,3}};

    cout << Szukaj(tablica, 8, 7);

    return 0;
}

short SzukajKw(short tab[][7], int x, int y, int m)
{
    if (m == 1)
        return 1;

    for (int i = x + 1; i < x + m; i++)
        for (int j = y + 1; j < y + m; j++)
            if (tab[i][j] != 1)
                return 0;

    return m;
}

short Szukaj(short tab[][7], int a, int b)
{
    short max = 0;
    int rozm = 0;

    for (int i = 0; i < a; i++)
    {
        for (int j = 0; j < b; j++)
        {
            if (tab[i][j] == 1)
            {
                rozm++;

                if (i + rozm - 1 <= a)
                    if (max < SzukajKw(tab, i, j - rozm + 1, rozm))
                        max = SzukajKw(tab, i, j - rozm + 1, rozm);
            }

            else
                rozm = 0;
        }

        rozm = 0;
    }

    return max;
}
0

Dzięki kolego, sam rozkminiałem to w podobny sposób, ale zawsze działało nie tak jak to sobie zakładałem.

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0