[C++] Tablica dwuwymiarowa i wyznaczenie maksymalnego pola.

[uchym]

Witam, mam nastepujacy problem, próbuje (mam za zadanie) napisac algorytm w c++, ktory dla dwuwymiarowej tablicy wyznacza maksymalne pole kwadratu o zadanym rozmiarze
Kwadrat ma lezeć wewnatrz tablicy.
Jego pole to suma elementow tablicy zawartych w kwadracie.

Kod: Zaznacz cały

#include <math.h>
#include <iostream>
#include <cstdlib>
using namespace std;

int main()
{
	
	//k - liczba kolumn
	//w - liczba wierszy
	//i - licznik i nr wiersza
	//j - nr kolumny w macierzy
	//r - rozmiar kwadratu
	int i,j,k,w;
	int tab[20][20];
	cout<<"Podaj liczbe kolumn tablicy i liczbe wierszy? "<<endl;
	cin>>k>>w;
	cout<<"Podaj rozmiar szukanego kwadratu? "<<endl;
	int r;
	cin>>r;
	
	cout<<"Tak wyglada tablica na poczatku:"<<endl;
		for(i=0;i<=k-1;i++)
			{
				for(j=0;j<=w-1;j++)
					{
						//wygenerowanie liczb z zakresu [-9; 9]
      					tab[i][j]=rand()%19-9; 
      					//wyświetlenie wylosowanej liczby
      						if(tab[i][j]>=0)
      							{
      							cout<<" "<<tab[i][j]<<" ";
							    }
							    else
							    {
							    cout<<tab[i][j]<<" ";
								}
					}
					cout<<endl;
			}
			cout<<endl; //linijka przerwy po 1 wypsaniu//
			
			
???????
			
	
	system("pause");
	return(0);
}

Pytanie do Was jaki najlepiej napisac kod ktory przeszukuje ta tablice w poszukiwaniu największego kwadratu o podanym rozmiarze ? nie moge kompletnie sobie z tym poradzic ;/ Macie jakies pomysly?

[lemoid]

Po pierwsze:
Jeżeli chcesz zrobić nową linię to użycie std::endl mija się troche z celem:

Jeżeli chciałbyś poprawić czytelność kodu zamiast:

Kod: Zaznacz cały

if(tab[i][j]>=0)
{
    cout<<" "<<tab[i][j]<<" ";
}
else
{
    cout<<tab[i][j]<<" ";
}

Można zrobić

Kod: Zaznacz cały

if(tab[i][j]>=0)
    cout<<" "<<tab[i][j]<<" ";
else
   cout<<tab[i][j]<<" ";

Teraz o Twoim problemie, podam Ci pomysł na bruteforce'owe rozwiązanie:

Mając macierz o wymiarach \(\displaystyle{ n \times n}\) chcesz znaleźć kwadrat o wymiarach \(\displaystyle{ m \times m}\), gdzie \(\displaystyle{ m <= n}\). Dosyć łatwo wyznaczyć ile jest takich "podkwadratów" (ile?).
Teraz wystarczy przejrzeć wszystkie te kwadraty i w każdym z nich zsumować te pola. W pseudokodzie będzie to wyglądało jakoś tak:

Kod: Zaznacz cały

// m - rozmiar "podkwadratu"
max = -inf;
row = 0;  
column = 0;
...
for (k = 0; k < ilosc_podkwadratow; k++)
{
    sum = 0;
    for (i = row; i < row + m; i++)
        for(j = column; j < column+m; j++)
            sum += tab[i][j];

    max = sum > max ? sum : max;
    if ( column + m == n)
    {
         row = 0;
         column++;

    }
}

[uchym]

ale nie koniecznie macierz musi byc \(\displaystyle{ n}\) na \(\displaystyle{ n}\) moze byc \(\displaystyle{ n}\) na \(\displaystyle{ p}\) np \(\displaystyle{ 5}\) na \(\displaystyle{ 7}\) i jakbysmy wczytali rozmiar kwadratu \(\displaystyle{ 3}\) (czyli \(\displaystyle{ 3}\) na \(\displaystyle{ 3}\)) to wtedy jak ma wygladac aalgorytm aby dobrze przeszukiwal i znajdowal najwiekszy kwadrat.
Np. tablica

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

suma tego kwadratu to: \(\displaystyle{ 40}\)

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

suma tego kw to: \(\displaystyle{ 42}\)
i tak trzeba przeszukac cala tablice i podac najwiekszy kwadrat tylko jak to zrobic ;/