Podtablica Identycznych Elementów

Cel

W tablicy wypełnionej liczbami całkowitymi należy znaleźć największy kwadrat w którym wszystkie elementy są równe pewnemu wybranemu. Rozwiązaniem jest algorytm o złożoności kwadratowej.

Przykład

Poniżej została przedstawiona przykładowa tablica. Poszukiwany jest kwadrat w którym wszystkie elementy będą miały wartość x = 1.

Dla podanego przykładu prawidłową odpowiedzią jest lewa, dolna podtablica 3×3. Jeśli jednak szukać podtablicy dla x = 7 to odpowiedzią jest 1×1, a dla wartości 3 nie ma odpowiedzi, ponieważ element ten nie występuje.

Algorytm

W celu wyznaczenia podtablicy dla pewnych zadanych wartości należy utworzyć tablicę o tej samej wielkości, a następnie wypełnić pierwszy wiersz oraz kolumnę według zasady, że jeśli na pozycji (i, j) stoi element x to należy wstawić 1, a w przeciwnym razie 0. Pozostałe elementy należy wypełnić przechodzą od lewej do prawej w kolejnych wierszach. Tym razem należy wybrać minimum spośród wartości powyżej pozycji (i, j) na lewo i na lewo do góry i dodać jeden jeśli element to x, a w przeciwnym razie postawić 0.

Dla podanej wcześniej tablicy zgodnie z przedstawionym algorytmem otrzymalibyśmy:

Na koniec w tablicy wystarczy wyszukać element o największej wartości - będzie to rozmiar maksymalnej, kwadratowej tablicy o wszystkich elementach x. Tutaj zgodnie z wcześniejszą odpowiedzią podtablica ma rozmiar 3×3.

Implementacja

Poniższa funkcja szukajPodtablicy() wyszukuje podtablicy w tablicy tab złożonej z elementów x. W wyniku zwracana jest liczba całkowita - szerokość maksymalnej, kwadratowej podtablicy.

1. int szukajPodtablicy(int** tab, int n, int m, int x) {
2.   int** kopia = new int*[m];
3.   for (int i = 0; i < m; i++)
4.   {
5.     kopia[i] = new int[n];
6.     for (int j = 0; j < n; j++)
7.       kopia[i][j] = (tab[i][j] == x) ? 1 : 0;
8.   }
10.   int maks = kopia[0][0], w;
11.   for (int i = 1; i < m; i++)
12.   {
13.     for (int j = 1; j < n; j++) {
14.       if (tab[i][j] == x)
15.       {
16.         w = min(kopia[i - 1][j - 1], kopia[i][j - 1]);
17.         w = min(kopia[i - 1][j], w);
18.         kopia[i][j] = w + 1;
19.         if (kopia[i][j] > maks)
20.           maks = kopia[i][j];
21.       } else {
22.         kopia[i][j] = 0;
23.       }
24.     }
25.   }
26.   return maks;
27. }

Na początku wykonana zostaje kopia tablicy, a następnie wypełnione zostają wszystkie elementy prócz pierwszego wiersza oraz pierwszej kolumny. W trakcie przypisywania nowej wartości dla pola na którym znajdowała się wartość x sprawdzane jest czy nie ma nowej wartości maksymalnej. Dzięki temu nie będzie trzeba przeglądać tablicy jeszcze raz. Na koniec zostaje zwrócona maksymalna znaleziona wartość.

Testowanie funkcji

Poniższy fragment kodu służy do wczytania danych od użytkownika, a następnie wypisania odpowiedzi.

1. int main() {
2.   int n, m, x;
3.   cout << "Podaj wymiary tablicy\n n x m = ";
4.   cin >> n >> m;
5.   cout << "Podaj elementy tablicy:" << endl;
6.   int** tablica = new int*[m];
7.   for (int i = 0; i < m; i++)
8.   {
9.     tablica[i] = new int[n];
10.     for (int j = 0; j < n; j++)
11.       cin >> tablica[i][j];
12.   }
13.   cout << "Podaj element:\n x = ";
14.   cin >> x;
15.   int wynik = szukajPodtablicy(tablica, n, m, x);
16.   cout << "Maksymalna podtablica ma wymiary:\n";
17.   cout << wynik << " x " << wynik;
18.   system("pause");
19.   return 0;
20. }

• Kod źródłowy Implementacja