//submatrix #1441 #include #include #include using namespace std; string fisier="submatrix"; ifstream fin(fisier+".in"); ofstream fout(fisier+".out"); int n, dp[1001][1001]; bool mat[1001][1001]; /* problema clasica // imi bordez initial matricea cu elementele de pe prima linia si prima coloana; verificarile pe aceste pozitii ar fi inutile; // pentru fiecare alt element, verific care este lungimea laturii celui mai mic patrat din care fac parte elementele din "spatele lui"; fie minimul dintre lungime laturilor verifcatex, acest fapt ne garanteaza garanteaza pentru elementul curent o lungime x+1; |element de verificat element de verificat| |element de verificat element curent | // la final pe pozitia (i, j) a matricei dp[][] v-a fi memorata lungimea maxima a laturii patratului ce contine elemenutul (i, j), luand in calcul strict elementele din submatricea (0,0)-(i,j) // parcurg matricea si afisez cea mai mare valoare gasita; */ void citire() { fin>>n; for (int i=1; i<=n; ++i) for (int j=1; j<=n; ++j) fin>>mat[i][j]; } void construire_margini() { for (int i=1; i<=n; ++i) { dp[i][1]=mat[i][1]; dp[1][i]=mat[1][i]; } } void rezolvare() { construire_margini(); int rezultat=0; for (int i=2; i<=n; ++i) { for (int j=2; j<=n; ++j) { if (mat[i][j]) { dp[i][j]=min(dp[i-1][j], min(dp[i-1][j-1], dp[i][j-1]))+1; if (dp[i][j]>rezultat) rezultat=dp[i][j]; } else dp[i][j]=0; } } fout<