Costache Radu - Mihai (radu_msk) 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.
Cerința
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
9puncte:1 ≤ N, M ≤ 5 - Pentru alte teste în valoare de
18puncte:N = 1 - Pentru alte teste în valoare de
36de puncte elementele din matrice suntDISTINCTE
Exemplu:
yinyang.in
2 3 1 2 4 3 5 6
yinyang.out
0
Explicație
Matricea dată este matrice yin-yang.
yinyang.in
2 3 6 6 5 4 6 2
yinyang.out
3
Explicație
Operațiile pot fi următoarele:
swap(linia 1 , linia 2),
swap(coloana 2, coloana 3),
swap(coloana 1, coloana 2).
Matricea dată va ajunge la final în forma yin-yang:
