# PBinfo #1787 – Mapal – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

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

## Cod sursă C++

```cpp
#include <iostream>
#include <fstream>
#include <bitset>
#include <string>
#define DN 1005
using namespace std;
int n,q,rez,cnt[2],x;
string m[DN];
bitset<DN> viz[DN],l,c;
void dfs(int a,int b) {
  ++cnt[m[a][b]-'0'];
  viz[a][b]=1;
  if(c[b] && !viz[n-a-1][b]) dfs(n-a-1,b);
  if(l[a] && !viz[a][n-b-1]) dfs(a,n-b-1);
}
int main() {
  ifstream f("mapal.in");
  ofstream g("mapal.out");
  f>>n;
  for(int i=0; i<n; ++i) f>>m[i];
  for(f>>q;q--;) {f>>x; --x; l[x]=1;}
  for(f>>q;q--;) {f>>x; --x; c[x]=1;}
  for(int i=0; i<n; ++i) for(int j=0; j<n; ++j) if(!viz[i][j] && (l[i] || c[j])) {
    cnt[0]=cnt[1]=0;
    dfs(i,j);
    rez+=min(cnt[0],cnt[1]);
  }
  g<<rez;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/1787)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/1787/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-1787/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)