Probleme clasice cu matrici
Această lecție reunește cele mai frecvente probleme cu matrici care apar la concursuri. Fiecare combină parcurgeri, condiții și tehnici din lecțiile anterioare.
Problema 1: Căutarea unui element
Verificăm dacă o valoare x există în matrice și,
dacă da, pe ce poziție.
#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");
int a[101][101];
int n, m;
int main()
{
fin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
fin >> a[i][j];
int x;
fin >> x;
int gasit = 0;
for (int i = 1; i <= n && gasit == 0; i++)
for (int j = 1; j <= m && gasit == 0; j++)
if (a[i][j] == x) {
fout << "Gasit pe linia " << i << " coloana " << j;
gasit = 1;
}
if (gasit == 0)
fout << "Nu exista";
return 0;
}Problema 2: Matrice simetrică
O matrice pătratică este simetrică față de
diagonala principală dacă a[i][j] == a[j][i] pentru
orice i și j.
Simetrică: Nu e simetrică:
1 2 3 1 2 3
2 4 5 4 5 6
3 5 6 7 8 9int simetrica = 1;
for (int i = 1; i <= n && simetrica; i++)
for (int j = i + 1; j <= n && simetrica; j++)
if (a[i][j] != a[j][i])
simetrica = 0;
if (simetrica)
fout << "DA";
else
fout << "NU";Optimizare: verificăm doar elementele
deasupra diagonalei principale
(j > i). Dacă a[i][j] == a[j][i]
pentru toate, matricea e simetrică.
Problema 3: Linia cu cele mai multe elemente pare
int maxPare = 0;
int linieSol = 1;
for (int i = 1; i <= n; i++) {
int pare = 0;
for (int j = 1; j <= m; j++)
if (a[i][j] % 2 == 0)
pare++;
if (pare > maxPare) {
maxPare = pare;
linieSol = i;
}
}
fout << "Linia " << linieSol << " cu " << maxPare << " elemente pare";Problema 4: Coloana cu suma minimă
int minSuma = 0;
for (int i = 1; i <= n; i++)
minSuma = minSuma + a[i][1];
int colSol = 1;
for (int j = 2; j <= m; j++) {
int suma = 0;
for (int i = 1; i <= n; i++)
suma = suma + a[i][j];
if (suma < minSuma) {
minSuma = suma;
colSol = j;
}
}
fout << "Coloana " << colSol << " cu suma " << minSuma;Problema 5: Înlocuirea elementelor negative cu zero
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (a[i][j] < 0)
a[i][j] = 0;Problema 6: Numărare elemente distincte în matrice
Folosim un vector de frecvență:
int fr[10001];
int cnt = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
if (fr[a[i][j]] == 0)
cnt++;
fr[a[i][j]]++;
}
fout << cnt;Problema 7: Șah - colorarea tablei
Pe o tablă de șah n x n, poziția
(i, j) este albă dacă (i + j) % 2 == 0
și neagră dacă (i + j) % 2 == 1 (sau invers).
n = 4:
A N A N
N A N A
A N A N
N A N ASuma elementelor de pe pozițiile “albe”:
int sumaAlbe = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if ((i + j) % 2 == 0)
sumaAlbe = sumaAlbe + a[i][j];Problema 8: Maximul pe fiecare linie
Construim un vector cu maximul fiecărei linii:
int maxLinie[101];
for (int i = 1; i <= n; i++) {
maxLinie[i] = a[i][1];
for (int j = 2; j <= m; j++)
if (a[i][j] > maxLinie[i])
maxLinie[i] = a[i][j];
}Problema 9: Punct șa
Un element a[i][j] este punct
șa dacă este minim pe linia lui și
maxim pe coloana lui (sau invers).
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
// Verificăm dacă a[i][j] e minim pe linia i
int minLinie = 1;
for (int k = 1; k <= m; k++)
if (a[i][k] < a[i][j])
minLinie = 0;
// Verificăm dacă a[i][j] e maxim pe coloana j
int maxCol = 1;
for (int k = 1; k <= n; k++)
if (a[k][j] > a[i][j])
maxCol = 0;
if (minLinie && maxCol)
fout << "Punct sa: a[" << i << "][" << j << "] = " << a[i][j] << endl;
}Ce este un punct șa?
Numele vine de la forma unei șei de cal: minimă într-o direcție (pe linie) și maximă în cealaltă (pe coloană). Este un concept important în teoria jocurilor și optimizare.
Nu orice matrice are punct șa. O matrice poate avea zero, unul sau mai multe.
Problema 10: Matrice pătratică magică
O matrice este magică dacă suma pe fiecare linie, fiecare coloană și cele două diagonale este aceeași.
int sumaDiagP = 0;
for (int i = 1; i <= n; i++)
sumaDiagP = sumaDiagP + a[i][i];
int magica = 1;
// Verificăm liniile
for (int i = 1; i <= n && magica; i++) {
int suma = 0;
for (int j = 1; j <= n; j++)
suma = suma + a[i][j];
if (suma != sumaDiagP) magica = 0;
}
// Verificăm coloanele
for (int j = 1; j <= n && magica; j++) {
int suma = 0;
for (int i = 1; i <= n; i++)
suma = suma + a[i][j];
if (suma != sumaDiagP) magica = 0;
}
// Verificăm diagonala secundară
int sumaDiagS = 0;
for (int i = 1; i <= n; i++)
sumaDiagS = sumaDiagS + a[i][n + 1 - i];
if (sumaDiagS != sumaDiagP) magica = 0;
if (magica) fout << "DA";
else fout << "NU";Problema 11: Interschimbarea a două linii
int l1, l2;
fin >> l1 >> l2;
for (int j = 1; j <= m; j++) {
int aux = a[l1][j];
a[l1][j] = a[l2][j];
a[l2][j] = aux;
}Problema 12: Interschimbarea a două coloane
int c1, c2;
fin >> c1 >> c2;
for (int i = 1; i <= n; i++) {
int aux = a[i][c1];
a[i][c1] = a[i][c2];
a[i][c2] = aux;
}Greșeli frecvente
1. Confuzia linie/coloană la verificări
La “minim pe linie” parcurgem coloanele (j). La
“maxim pe coloană” parcurgem liniile (i).
2. Matrice magică - uitarea diagonalei secundare
Verificăm linii + coloane dar uităm diagonala secundară.
3. Punct șa - verificare incompletă
Trebuie verificat dacă este minim pe întreaga linie și maxim pe întreaga coloană, nu doar comparații locale.
Ce să reții
- Căutare: parcurgem tot și comparăm.
- Simetrie:
a[i][j] == a[j][i]pentru deasupra diagonalei. - Linie/coloană cu proprietate: buclă pe linii/coloane cu calcul intern.
- Punct șa: minim pe linie și maxim pe coloană (sau invers).
- Matrice magică: aceeași sumă pe linii, coloane, diagonale.
- Tablă de șah:
(i + j) % 2determină culoarea. - Interschimbare linii/coloane: parcurgem și facem swap element cu element.