Cerința

Se dă o matrice binară (valori 0 și 1). Să se determine care este latura maximă a unui pătrat cu proprietatea că acesta are pe marginea sa doar valori 1.

Date de intrare

Fișierul de intrare lsq.in conține pe prima linie numerele N și M, reprezentând numărul de linii și numărul de coloane ale matricei, apoi N linii, pe fiecare câte M valori 0 sau 1, neseparate prin niciun spațiu, reprezentând elementele matricei..

Date de ieșire

Fișierul de ieșire lsq.out va conține pe prima linie numărul L, reprezentând lungimea maximă a laturii unui pătrat ce conține doar 1 pe marginea sa.

Restricții și precizări

1 ≤ N, M ≤ 1000
Se consideră pătrat și cel de latură 1 (conține doar un element).

Exemplu

lsq.in

lsq.out

Explicație

0 0 0 0 0 0 0
0 1 1 1 1 0 0
0 1 0 1 1 1 1
0 1 0 0 1 0 1
0 1 1 1 1 1 1
0 0 0 0 0 1 1
0 0 0 0 0 1 1

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 LSQ:

#include <bits/stdc++.h>

#define Nmax 1005

using namespace std;

ifstream fin("lsq.in");
ofstream fout("lsq.out");

int N, M;
char C[Nmax];
int A[Nmax][Nmax];
int LRU[Nmax][Nmax], CRU[Nmax][Nmax], LDL[Nmax][Nmax], CDL[Nmax][Nmax];
set <int> S;
vector <int> E[Nmax];
int ans;

int main()
{
    fin >> N >> M;
    for(int i = 1; i <= N; i++)
    {
        fin >> (C + 1);
        for(int j = 1; j <= M; j++)
            A[i][j] = C[j] - '0';
    }
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= M; j++)
            if(A[i][j] == 1)
                LDL[i][j] = 1 + LDL[i][j - 1], CDL[i][j] = 1 + CDL[i - 1][j];
    for(int i = N; i >= 1; i--)
        for(int j = M; j >= 1; j--)
            if(A[i][j] == 1)
                LRU[i][j] = 1 + LRU[i][j + 1], CRU[i][j] = 1 + CRU[i + 1][j];
    int ans = 0;
    for(int i = N; i >= 1; i--)
        for(int j = M; j >= 1; j--)
            for(int L = min(LDL[i][j], CDL[i][j]); L > ans; L--)
                if(L <= min(LRU[i - L + 1][j - L + 1], CRU[i - L + 1][j - L + 1]))
                    ans = L;
    fout << ans << "\n";
    return 0;
}

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 #2724 LSQ

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2724 LSQ 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 #2724 LSQ