Cerința
Considerăm codificarea binară a caracterelor, în care fiecărui simbol îi revine reprezentarea pe 8 biți a codului său ASCII. De exemplu, caracterului ’A’, având codul ASCII 65, îi va corespunde reprezentarea binară 01000001.
Scrieți un program care citește din fișierul convert_submatrix.in un șir s format din n ≤ 100 caractere și construiește o matrice M cu n linii și 8 coloane, linia i a matricii reprezentând codificarea binară a caracterului de pe poziția i din șir. Se cere determinarea dimensiunii celei mai mari submatrice pătratice a lui M, care conține elemente cu aceeași valoare (fie 0, fie 1). Valoarea determinată se scrie în fișierul convert_submatrix.out.
Date de intrare
Fișierul de intrare convert_submatrix.in conține pe prima linie șirul s format din cel mult 100 de caractere.
Date de ieșire
Fișierul de ieșire convert_submatrix.out va conține pe prima linie numărul rez, reprezentând dimensiunea celei mai mari submatrici pătratice a lui m conținând elemente cu aceeași valoare (fie 0, fie 1).
Restricții și precizări
- lungimea șirului:
1 ≤ n ≤ 100 - șirul poate să conțină:
ABCDEFGHIJKLMNOPQRSTUVXYZabcdefghijklmnopqrstuvxyz0123456789 `~,./;:][}{+_=-|!#$%^&*()
Exemplul 1:
convert_submatrix.in
IDEEA
convert_submatrix.out
3
Explicație
Matricea corespunzătoare șirului citit este:
\begin{pmatrix}
0&1&0&0&1&0&0&1\\
0&1&0&0&0&1&0&0\\
0&1&0&0&0&1&0&1\\
0&1&0&0&0&1&0&1\\
0&1&0&0&0&0&0&1
\end{pmatrix}
Se observă că dimensiunea celei mai mari submatrici pătratice a lui m conținând elemente cu aceeași valoare este 3.
Exemplul 2:
convert_submatrix.in
AAAyyyy
convert_submatrix.out
4
Explicație
Matricea corespunzătoare șirului citit este:
\begin{pmatrix}
0&1&0&0&0&0&0&1\\
0&1&0&0&0&0&0&1\\
0&1&0&0&0&0&0&1\\
0&1&1&1&1&0&0&1\\
0&1&1&1&1&0&0&1\\
0&1&1&1&1&0&0&1\\
0&1&1&1&1&0&0&1\\
\end{pmatrix}
Se observă că dimensiunea celei mai mari submatrici pătratice a lui m conținând elemente cu aceeași valoare este 4.
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 convert_submatrix:
#include <bits/stdc++.h>
using namespace std;
#define smax 101
ifstream f("convert_submatrix.in");
ofstream g("convert_submatrix.out");
char sir[smax];
bool matrice[smax][8];
void conversie_c(char c, bool binar[8])
{
int i;
for (i = 0; i < 8; i++)
binar[7 - i] = c & (1 << i);
}
void conversie_sir(char* s, bool binar[smax][8])
{
int i;
for (i = 0; s[i]; i++)
conversie_c(s[i], binar[i]);
}
int mini(int x, int y, int z)
{
int mi=x;
if(y<mi)
mi=y;
if(z<mi)
mi=z;
return mi;
}
int maxi(int x, int y, int z)
{
int ma=x;
if(y>ma)
ma=y;
if(z>ma)
ma=z;
return ma;
}
int submatrice(int nrl, int nrc, bool m[smax][8])
{
int i, j, rez = 1;
int a[smax][8], b[smax][8];
for (i = 1; i < nrl; i++)
{
a[i][0] = !m[i][0];
b[i][0] = m[i][0];
}
for (j = 0; j < nrc; j++)
{
a[0][j] = !m[0][j];
b[0][j] = m[0][j];
}
for (i = 1; i < nrl; i++)
for (j = 1; j < nrc; j++)
{
a[i][j] = (m[i][j] ? 0 : mini(a[i - 1][j], a[i][j - 1], a[i - 1][j - 1]) + 1);
b[i][j] = (m[i][j] ? mini(b[i - 1][j], b[i][j - 1], b[i - 1][j - 1]) + 1 : 0);
rez = maxi(rez, a[i][j], b[i][j]);
}
return rez;
}
int main()
{
f.get(sir,100);
conversie_sir(sir, matrice);
g<<submatrice(strlen(sir),8,matrice);
f.close();g.close();
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 
.
Rezolvarea problemei #3296 convert_submatrix
Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #3296 convert_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!