Pe un teren de formă dreptunghiulară format din L linii și C coloane sunt plantate M mine. Liniile sunt numerotate de sus în jos cu valori de la 1 la L iar coloanele sunt numerotate de la stânga la dreapta cu valori de la 1 la C. Deoarece războiul s-a terminat, specialiștii vor să demineze terenul și să-l redea utilizării publice. Mutarea unei mine reprezintă operația de transfer a unei mine de la linia x1 și coloana y1 la o poziție liberă, dată de linia x2 și coloana y2, unde 1 ≤ x1, x2 ≤ L și 1 ≤ y1, y2 ≤ C. Deoarece mutarea unei mine este periculoasă, trebuie determinat numărul minim de mine care trebuie mutate din poziția inițială astfel încât toate minele de pe teren să fie așezate unele lângă altele într-o zonă compactă dreptunghiulară, oriunde în cadrul terenului dat, pentru ca apoi să fie detonate împreună.
Spre exemplu: dacă L = 4, C = 5, M = 8 și minele sunt așezate inițial conform figurii de mai jos (zonele colorate cu negru arată pozițiile minelor), pentru a se ajunge la o așezare a minelor într-o zonă compactă de formă dreptunghiulară numărul minim de mine mutate este 3.
Cerința
Cunoscând numărul de linii L și de coloane C ale terenului minat, numărul de mine M, precum și poziția fiecărei mine, să se scrie un program care determină:
1. linia sau liniile pe care se găsesc cele mai multe mine;
2. numărul minim de mine mutate, pentru ca toate minele de pe teren să fie așezate într-o zonă compactă cu formă dreptunghiulară.
Date de intrare
Fișierul de intrare este deminare.in și conține:
- pe prima linie numărul natural V a cărui valoare poate fi doar 1 sau 2;
- pe a doua linie două numere naturale L și C, cu semnificația din enunț;
- pe a treia linie numărul natural M, cu semnificația din enunț;
- pe fiecare din următoarele M linii, câte o pereche de valori xi și yi, 1 ≤ i ≤ M, reprezentând linia, respectiv coloana, unde se află o mină;
Numerele aflate pe aceeași linie a fișierului sunt separate prin câte un spațiu.
Date de ieșire
Fișierul de ieșire este deminare.out.
Dacă valoarea lui V este 1 atunci prima linie a fișierului de ieșire va conține numărul liniei pe care se găsesc cele mai multe mine. Dacă există două sau mai multe astfel de linii, se vor afișa toate numerele acestora, în ordine crescătoare, separate prin câte un spațiu.
Dacă valoarea lui V este 2 atunci fișierul de ieșire va conține pe prima linie numărul minim cerut de mine mutate. Dacă minele nu pot fi așezate într-o zonă compactă de formă dreptunghiulară, în fișierul de ieșire se va scrie valoarea -1.
Restricții și precizări
1 ≤ L, C ≤ 5001 ≤ M ≤ L • C- O zonă în care se află mine așezate pe coloane consecutive, pe aceeași linie sau așezate pe linii consecutive, pe aceeași coloană se consideră că formează o zonă compactă de formă dreptunghiulară.
- O zonă compactă de formă dreptunghiulară poate avea numărul de linii ocupate egal cu numărul de coloane ocupate.
- Pentru teste valorând
20de puncte, avemV = 1 - Pentru teste valorând
70de puncte, avemV = 2 - Pentru teste valorând
20de puncte, avemV = 2șiL • C ≤ 10.000 - Pentru teste valorând
32de puncte, avemV = 2șiL • C ≤ 100.000 - În concurs s-au acordat
10puncte din oficiu. Aici se acordă pentru exemplele din enunț.
Exemplul 1:
deminare.in
1 4 5 8 1 2 1 5 2 1 3 2 3 5 4 3 4 4 4 5
deminare.out
4
Explicație
V = 1, deci se rezolvă doar cerința 1. L = 4, C = 5, M = 8.
Minele sunt plasate la pozițiile (1,2), (1,5), (2,1), (3,2), (3,5), (4,3), (4,4) și (4,5).
Pe linia 1 sunt amplasate 2 mine;
Pe linia 2 este amplasată 1 mină;
Pe linia 3 sunt amplasate 2 mine;
Pe linia 4 sunt amplasate 3 mine;
Deci, există o singură linie pe care sunt amplasate un număr maxim de mine și anume linia 4.
Exemplul 2:
deminare.in
2 4 5 8 1 2 1 5 2 1 3 2 3 5 4 3 4 4 4 5
deminare.out
3
Explicație
V = 2, deci se rezolvă doar cerința 2. L = 4, C = 5, M = 8.
Minele sunt plasate la pozițiile (1,2), (1,5), (2,1), (3,2), (3,5), (4,3), (4,4) și (4,5).
Pentru a obține o zonă compactă de formă dreptunghiulară trebuie mutate minimum 3 mine. O variantă posibilă este:
Mina de la poziția (1,2) se mută la poziția (3,3);
Mina de la poziția (1,5) se mută la poziția (3,4);
Mina de la poziția (2,1) se mută la poziția (4,2);
Se obține o zonă compactă de formă dreptunghiulară, având colțul din stânga sus la poziția (3,2) și colțul din dreapta jos la poziția (4,5).
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 deminare:
// prof. Chesca Ciprian - 100 p
// cu constructia matricei sumelor partiale O(lc) si O(sqrt(m))
// sursa cu assert
#include <fstream>
#include <cassert>
using namespace std;
int a[501][501];
int w[501],mat[501][501];
int main()
{
int l,c,i,j,k,m,x,y,maxl,s,v,maxm,ls,cs,ok,i1,j1;
/* l = linii
c = coloane
m = numar de mine
x,y = coordonate mina
v = varianta
maxm = numarul maxim de mine dintr-o zona de scanare
maxl = numarul maxim de mine de pe o linie
k = contorul pentru numararea minelor dintr-o zona de scanare
ok = indicator pentru a determina daca problema are solutie
ls, cs = numarul de linii si coloane al zonei de scanare
*/
ifstream f("deminare.in");
ofstream g("deminare.out");
// citire date de intrare
f >> v;
assert(v>=1 && v <=2);
f >> l >> c;
assert(l>=1 && l<=500);
assert(c>=1 && c<=500);
f >> m;
assert(m>=1 && m<=l*c);
int perechi = 0;
while(f>>x>>y)
{
assert(x>=1 && x<=l);
assert(y>=1 && y<=c);
perechi++;
a[x][y]=1;
}
// prima cerinta
if (v == 1)
{
// cerinta = care este linia pe care se gasesc cele mai multe mine
// daca sunt mai multe linii se afiseaza toate in ordine crescatoare cu spatiu intre ele
// aflu numarul de mine pe linii
for(i=1;i<=l;i++)
{
s=0;
for(j=1;j<=c;j++)
if(a[i][j]==1) s++;
w[i]=s;
}
// aflu maximul de mine de pe o linie
maxl=w[1];
for(i=1;i<=l;i++)
if (w[i]>maxl) maxl=w[i];
// afisez linia(iile)
for(i=1;i<=l;i++)
if (w[i]==maxl) g << i << " ";
g << "\n";
}
// cerinta a doua
if(v == 2)
{
// cerinta = numarul minim de mutari de mine astfel incat sa se obtina o suprafata dreptunghiulara
// aflu numarul de mine in submatricile (1,1) si (i,j) cu (i,j) de la 1<=i<=l si l<=j<=c
// am renuntat sa calculez separat prima linie si prima coloana pentru ca oricum valorile sunt 0
for(i=1;i<=l;i++)
for(j=1;j<=c;j++)
mat[i][j]=a[i][j]+mat[i-1][j]+mat[i][j-1]-mat[i-1][j-1];
// descompun m in produs de 2 numere naturale
ok = 0; maxm = 0;
for(i=1;i*i<=m;i++)
if (m%i==0)
{
ls = i;cs = m/i;
// incep scanarea directa
if (ls <= l && cs <= c)
{
ok = 1;
for(i1=1;i1<=l-ls+1;i1++)
for(j1=1;j1<=c-cs+1;j1++)
{
k = mat[i1+ls-1][j1+cs-1] - mat[i1+ls-1][j1-1] - mat[i1-1][j1+cs-1] + mat[i1-1][j1-1];
if (k > maxm) maxm = k;
}
}
ls = m/i;cs = i;
// si inversa
if (ls <= l && cs <= c)
{
ok = 1;
for(i1=1;i1<=l-ls+1;i1++)
for(j1=1;j1<=c-cs+1;j1++)
{
k = mat[i1+ls-1][j1+cs-1] - mat[i1+ls-1][j1-1] - mat[i1-1][j1+cs-1] + mat[i1-1][j1-1];
if (k > maxm) maxm = k;
}
}
}
if (!ok) g << "-1\n";
else g << m - maxm << "\n";
if (perechi!=m) g << "eroare!";
}
return 0;
}
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 
.
Rezolvarea problemei #2961 deminare
Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2961 deminare 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!