Fişierul intrare/ieşire:yinyang.in, yinyang.outSursăOJI 2019, clasa a 10-a
AutorEugenie Daniel PosdarascuAdăugată detamionvTamio Vesa Nakajima tamionv
Timp execuţie pe test2 secLimită de memorie256000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Yinyang

Se dă o matrice A cu N linii şi M coloane, cu valori cuprinse între 1 şi N * M inclusiv, nu neapărat distincte. O operaţie constă în selectarea a două linii sau două coloane consecutive şi interschimbarea acestora (swap). O matrice yin-yang este o matrice în care A[i][j] ≥ A[i][j–1], pentru orice pereche (i, j) cu 1 ≤ i ≤ N şi 2 ≤ j ≤ M şi A[i][j] ≥ A[i–1][j], pentru orice pereche (i, j) cu 2 ≤ i ≤ N şi 1 ≤ j ≤ M.
Să se determine numărul minim de operaţii necesare pentru a transforma matricea dată într-o matrice yin-yang.

Date de intrare

În fişierul de intrare yinyang.in se află scrise pe prima linie numerele naturale N şi M, cu semnificaţia din enunţ. Pe fiecare dintre următoarele N linii se află câte M numere naturale, reprezentând elementele matricei date A. Numerele aflate pe aceeaşi linie a fişierului sunt separate prin câte un spaţiu.

Date de ieşire

În fişierul yinyang.out se va scrie numărul minim de operaţii cerut sau -1 dacă nu există soluţie.

Restricţii şi precizări

  • 1 ≤ N, M ≤ 100
  • Pentru teste în valoare de 9 puncte: 1 ≤ N, M ≤ 5
  • Pentru alte teste în valoare de 18 puncte: N = 1
  • Pentru alte teste în valoare de 36 de puncte elementele din matrice sunt distincte
  • 10 puncte sunt din oficiu (corespund unor teste egale cu exemplul).

Exemple

yinyang.in
yinyang.out
Explicaţii
2 3
1 2 4
3 5 6
0
Matricea dată este matrice yin-yang
2 3
6 6 5
4 6 2
3
Operaţiile pot fi următoarele:
swap(linia 1 , linia 2),
swap(coloana 2, coloana 3),
swap(coloana 1, coloana 2).
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?