Pietrele preţioase au fascinat omenirea încă din timpuri străvechi iar cele mai renumite dintre ele, cristalele, au devenit atât simbolul durităţii cât şi al eternităţii. În urma unui studiu ştiinţific, pe un eşantion de formă dreptunghiulară se pot observa diferite tipuri de molecule, dispuse într-o geometrie perfectă, pe M rânduri a câte N molecule fiecare, aliniate una lângă alta. O formaţiune cristalizabilă este alcătuită din 3 molecule de acelaşi tip, învecinate două câte două, având una dintre cele patru forme din imaginea alăturată (fig.1).
Fiecare formaţiune este înconjurată de jur-împrejur, ca în fig.2, de un înveliş special format şi el din molecule identice, de alt tip decât cele din formaţiunea cristalizabilă pe care o înconjoară şi o izolează de restul formaţiunilor moleculare. În acest fel, fiecare moleculă din formaţiunea cristalizabilă se învecinează la Nord, Sud, Est şi Vest cu o moleculă din aceeaşi formaţiune cristalizabilă sau cu o moleculă din învelişul special.
Fiecare formaţiune cristalizabilă se bombardează cu raze X şi în acest fel are loc cristalizarea, proces prin care învelişul special se extinde peste formaţiunea cristalizabilă pe care o înconjoară, formând o singură structură din care se va dezvolta cristalul.
Cerințe
- Determinaţi numărul formaţiunilor cristalizabile ce pot fi identificate pe eşantionul analizat.
- Afişaţi eşantionul rezultat după cristalizare.
Date de intrare
Fișierul de intrare cristale.in conține pe prima linie un număr natural c reprezentând cerinţa care trebuie să fie rezolvată (1 sau 2). Pe cea de-a doua linie se află două numere naturale M şi N, separate printr-un spaţiu, având semnificaţia din enunţ. Pe următoarele M linii se află câte N numere naturale, separate prin câte un spaţiu, reprezentând moleculele din eşantionul analizat.
Date de ieșire
Dacă valoarea lui c este 1, atunci se va rezolva numai cerinţa 1, caz în care pe prima linie a fişierului cristale.out va fi scris un număr natural reprezentând numărul formaţiunilor cristalizabile identificate pe eşantionul analizat. Dacă valoarea lui c este 2, atunci se va rezolva numai cerinţa 2. În acest caz, fişierul de ieşire cristale.out va conţine pe fiecare dintre primele M linii, câte N numere naturale separate prin câte un spaţiu, reprezentând moleculele eşantionului rezultat după cristalizare.
Restricții și precizări
4 ≤ M,N ≤ 800şi tipul fiecărei molecule este exprimat printr-un număr natural din intervalul[1,16];- pe marginea eşantionului nu pot fi identificate formaţiuni cristalizabile;
există cel puţin o formaţiune cristalizabilă pe eşantionul analizat; - eşantionul nu conţine formaţiuni cristalizabile lipite (cu celule vecine pe una din cele patru direcţii);
- pentru rezolvarea corectă a cerinţei 1 se acordă 30% din punctaj, iar pentru rezolvarea corectă a cerinţei 2 se acordă 70% din punctaj.
Exemplul 1
cristale.in
1 6 8 5 6 6 1 5 2 6 5 6 9 9 6 1 7 1 2 6 6 9 6 3 4 1 6 2 2 6 3 4 7 4 2 8 8 2 4 7 7 4 6 8 2 7 2 4 4 2 5
cristale.out
2
Explicație
Se va rezolva cerinţa 1 a problemei.
Eşantionul are 6 rânduri cu câte 8 molecule pe fiecare rând. Pe acest eşantion observăm o formaţiune cristalizabilă cu celule de tip 9, izolată de învelişul special format din celule identice, toate de tip 6 şi o formaţiune cristalizabilă cu celule de tip 7, izolată de învelişul special format din celule identice, toate de tip 4.
Formaţiunea de 3 molecule de tip 8 nu este o formaţiune cristalizabilă întrucât se află pe marginea eşantionului.
Exemplul 2
cristale.in
2 6 8 5 6 6 1 5 2 6 5 6 9 9 6 1 7 1 2 6 6 9 6 3 4 1 6 2 2 6 3 4 7 4 2 8 8 2 4 7 7 4 6 8 2 7 2 4 4 2 5
cristale.out
5 6 6 1 5 2 6 5 6 6 6 6 1 7 1 2 6 6 6 6 3 4 1 6 2 2 6 3 4 4 4 2 8 8 2 4 4 4 4 6 8 2 7 2 4 4 2 5
Explicație
Se va rezolva cerinţa 2 a problemei.
După cristalizare, peste fiecare din cele două formaţiuni cristalizabile identificate se extinde învelişul din jurul lor.
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 Cristale:
#include <fstream>
#define ML 801
#define MC 801
using namespace std;
short int p[5][MC],lc[MC],lu[MC];
int m,n,np;
ifstream f("cristale.in");
ofstream g("cristale.out");
int f1(int li, int co)
{ int cp,cf;
cp=p[li][co];
cf=p[li][co-1];
if((cp==p[li][co+1])&&
(cp==p[li+1][co+1])&&
(cp!=cf)&&
(cf==p[li-1][co])&&
(cf==p[li-1][co+1])&&
(cf==p[li][co+2])&&
(cf==p[li+1][co+2])&&
(cf==p[li+2][co+1])&&
(cf==p[li+1][co]) )
{
p[li][co]=p[li][co+1]=p[li+1][co+1]=cf;
return 1;
}
return 0;
}
int f2(int li, int co)
{ int cp,cf;
cp=p[li][co];
cf=p[li][co-1];
if((cp==p[li][co+1])&&
(cp==p[li+1][co])&&
(cp!=cf)&&
(cf==p[li-1][co])&&
(cf==p[li-1][co+1])&&
(cf==p[li][co+2])&&
(cf==p[li+1][co+1])&&
(cf==p[li+2][co])&&
(cf==p[li+1][co-1]))
{
p[li][co]=p[li][co+1]=p[li+1][co]=cf;
return 1;
}
return 0;
}
int f3(int li, int co)
{ int cp,cf;
cp=p[li][co];
cf=p[li][co-1];
if((cp==p[li+1][co+1])&&
(cp==p[li+1][co])&&
(cp!=cf)&&
(cf==p[li-1][co])&&
(cf==p[li][co+1])&&
(cf==p[li+1][co+2])&&
(cf==p[li+2][co+1])&&
(cf==p[li+2][co])&&
(cf==p[li+1][co-1]))
{
p[li][co]=p[li+1][co+1]=p[li+1][co]=cf;
return 1;
}
return 0;
}
int f4(int li, int co)
{ int cp,cf;
cp=p[li][co];
cf=p[li][co-1];
if((cp==p[li+1][co])&&
(cp==p[li+1][co-1])&&
(cp!=cf)&&
(cf==p[li-1][co])&&
(cf==p[li][co+1])&&
(cf==p[li+1][co+1])&&
(cf==p[li+2][co])&&
(cf==p[li+2][co-1])&&
(cf==p[li+1][co-2]))
{
p[li][co]=p[li+1][co]=p[li+1][co-1]=cf;
return 1;
}
return 0;
}
void afis4_linii()
{ int i,j;
for(i=2;i<=2;i++)
{ g<<'\n';//fprintf(g,"\n");
for(j=1;j<=n-1;j++)
g<<p[i][j]<<' ';//fprintf(g,"%d ",p[i][j]);
g<<p[i][n];//fprintf(g,"%d",p[i][n]);
}
}
void copiere_linii_peste_cele_vechi()
{ int j;
for(j=1;j<=n;j++)
{
p[1][j]=p[2][j];
p[2][j]=p[3][j];
p[3][j]=p[4][j];
}
}
int main()
{
int i,j,idf,k,c;
f>>c>>m>>n;
for(i=1;i<=4;i++)
for(j=1;j<=n;j++)
f>>p[i][j];
int nr_linii=3;
if(c==2)
{for(j=1;j<=n-1;j++)
g<<p[1][j]<<' ';
g<<p[1][n];
}
do
{
i=2;
for (k=2;k<=n-1;k++) lu[k]=1;
{
for (k=2;k<=n-1;k++)
{
lc[k]=lu[k];
lu[k]=1;
}
for(j=2;j<=n-1;j++)
{
if(lc[j])
{
idf=1;
if(idf&&(j<n-1)&&f1(i,j))
{
np++;
lu[j]=lu[j+1]=lu[j+2]=0;
j+=2;
idf=0;
}
if(idf&&(j<n-1)&&f2(i,j))
{
np++;idf=0;
lu[j-1]=lu[j]=lu[j+1]=0;
j+=2;
}
if(idf&&(j<n-1)&&f3(i,j))
{
np++;idf=0;
lu[j-1]=lu[j]=lu[j+1]=lu[j+2]=0;
j+=1;
}
if(idf&&(j>2)&&f4(i,j))
{
np++;idf=0;
lu[j-2]=lu[j-1]=lu[j]=lu[j+1]=0;
j+=1;
}
}
}
}
if(c==2)
afis4_linii();
copiere_linii_peste_cele_vechi();
for(j=1;j<=n;j++)
f>>p[4][j];
nr_linii++;
i=1;
} while(nr_linii<m);
if(c==2)
{
for(i=2;i<=3;i++)
{ g<<'\n';
for(j=1;j<=n-1;j++)
g<<p[i][j]<<' ';
g<<p[i][n];
}
g<<'\n';
}
else
if(c==1)
g<<np<<'\n';
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 #1702 Cristale
Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1702 Cristale 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!