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

mapal.out

Explicație

Una dintre soluțiile pentru care liniile 1, 2, 4 și coloanele 1, 4 sunt palindrom e:

pre. 1111
0110
0000
1111

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Mapal:

#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;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1787 Mapal

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1787 Mapal de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1787 Mapal