Cerința
Marele inginer NN, a fost numit inspector general al barajelor. În prima zi de lucru el primește un sector dintr-un baraj de lângă un lac de acumulare care conține stricăciuni și are misiunea de a realiza un plan de reparații. În plus, costurile reparațiilor trebuie să fie minime. Sectorul din baraj poate fi reprezentat ca o matrice binară de NxN
. El a observat că liniile l1, l2 …, lk
și coloanele c1,c2, …, cl
sunt singurele care au stricăciuni. Pentru a le repara el trebuie să înlocuiască unele elemente din matrice astfel încât liniile și coloanele stricate să devină palindrom.
Ajutați-l pe NN să găsească numărul minim de înlocuiri și să dovedească că e maestru în baraje de toate felurile.
Date de intrare
Pe prima linie a fișierului mapal.in
se va afla N
reprezentând lățimea și lungimea barajului.
Pe următoarele N
linii se vor afla N
caractere, fiecare caracter aparținând mulțimii {0, 1}
și reprezentând elementul de pe linia i
și coloana j
a matricii care reprezintă barajul.
Pe următoarea linie se va afla L
, reprezentând numărul de linii stricate. Pe următoarea linie se vor afla L
numere reprezentând indicii liniilor stricate.
Pe următoarea linie se va afla C
, reprezentând numărul de coloane stricate. Pe următoarea linie se vor afla C
numere reprezentând indicii coloanelor stricate.
Date de ieșire
Pe singura linie a fișierului mapal.out
se va afișa numărul minim de înlocuiri astfel încât liniile și coloanele date să devină palindrom.
Restricții și precizări
N ≤ 1000
- Elementele matricii aparțin mulțimii
{0,1}
.
Exemplu:
mapal.in
4 1011 0111 0000 1010 3 1 2 4 2 1 4
mapal.out
4
Explicație
Una dintre soluțiile pentru care liniile 1
, 2
, 4
și coloanele 1
, 4
sunt palindrom e:
pre. 1111
0110
0000
1111