După ce a rezolvat problema propusă de tatăl sau, Robert a prins drag de algoritmică. După câteva probleme rezolvate a dat peste o problemă pe care nu a putut-o rezolva. Având o matrice pătratică cu elemente 0 și 1 el trebuie sa afle dimensiunea maximă a unei submatrice pătratice ce conține numai valori 1. Robert este foarte confuz, și vă roagă din nou să îl ajutați. Ca răsplată vă promite 100 de puncte dacă îl ajutați să rezolve și această problemă. Ce ziceți ? Îl ajutăm din nou ?

Cerința

Fiind dată o matrice pătratică de dimensiune n cu valori 0 și 1, să se determine dimensiunea maximă a unei submatrice ce conține numai valori 1.

Date de intrare

Fișierul de intrare submatrix.in conține pe prima linie numărul n reprezentând dimensiunea matricei. Următoarele n linii conțin câte n numere din mulțimea {0,1}.

Date de ieșire

Fișierul de ieșire submatrix.out va conține pe prima linie o valoare naturală L, reprezentând dimensiunea maxima a unei submatrice ce conține numai valori 1.

Restricții și precizări

1 ≤ n ≤ 1000
Pentru 10% din teste n≤10

Exemplul 1

submatrix.in

submatrix.out

Exemplul 2

submatrix.in

submatrix.out

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Submatrix:

//Solutie problema Matrice
//programare dinamica
//Complexitate N*N
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

#define dim 1009
using namespace std;
ofstream out("submatrix.out");

int a[dim][dim];
int dp[dim][dim];

int n ;
int sol = 0;

void read();
void debug();
void build();
void solve();

int main()
{
    read();
    build();
    solve();
   // debug();

    out << sol;
}

void read()
{
    ifstream in("submatrix.in");
    in >> n;

    for(int i = 1; i <=n; i++)
        for(int j = 1; j<=n; j++)
            in >> a[i][j];
}

void build()
{
    //first line
    for(int i = 1 ; i<=n ; i++)
        dp[1][i] = a[1][i];

    //first column
    for(int i = 1; i<=n; i++)
        dp[i][1] = a[i][1];
}

void solve()
{
    //pornim de la a[2][2]
    for(int i = 2; i<=n; i++)
        for(int j = 2; j<=n; j++)
        {
            if(a[i][j] == 1)
            {
              dp[i][j] = min(dp[i-1][j],min(dp[i-1][j-1],dp[i][j-1])) + 1;
            }
            else
            {
                dp[i][j] = 0;
            }
        }

    for(int i = 1 ; i<=n; i++)
        for(int j = 1 ; j<=n; j++)
            if(dp[i][j] > sol)
                sol = dp[i][j];
}

void debug()
{
    for(int i = 1;  i<=n ; i++)
    {
        for(int j = 1; j<=n; j++)
            cerr << dp[i][j] << " ";
        cerr << '\n';
    }
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1441 Submatrix

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1441 Submatrix de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1441 Submatrix