| Fişierul intrare/ieşire: | yinyang.in, yinyang.out | Sursă | OJI 2019, clasa a 10-a |
| Autor | Eugenie Daniel Posdarascu | Adăugată de |  Tamio Vesa Nakajima •tamionv |
| Timp execuţie pe test | 1 sec | Limită de memorie | 256000 kbytes |
| Scorul tău | N/A | Dificultate | N/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). |
