Rezolvare completă PbInfo #3435 foto1

O fotografie alb-negru a surprins imaginea fulgerelor pe cerul întunecat în timpul unei furtuni electrice. Mărită, fotografia arată ca un caroiaj format din mici pătrate identice, albe sau negre, dispuse alăturat pe N rânduri și M coloane, câte M pe fiecare rând. Pătratele albe formează fulgerele din fotografie, iar pătratele negre reprezintă cerul. În fotografie, nu există două pătrate albe dispuse alăturat pe același rând. Un fulger este format din pătrate albe situate pe rânduri consecutive care respectă următoarele condiții: a) pătratele albe situate pe două rânduri consecutive au un vârf comun sau o latură comună; b) un fulger poate avea un singur pătrat alb pe un rând. În fotografie, fulgerele sunt distincte, ele neavând pătrate albe cu laturi sau vârfuri comune. Înălțimea unui fulger este dată de numărul de pătrate albe ale acelui fulger.

Pentru a putea fi analizată de către programatori, fotografia este codificată cu ajutorul unui tablou bidimensional cu N linii și M coloane, ale cărui elemente sunt 0 și 1. Valoarea 0 este codificarea pătratului negru, iar valoarea 1 este codificarea pătratului alb.

Având codificarea, programatorii trebuie să găsească numărul maxim P de pătrate negre dispuse alăturat pe același rând, numărul de fulgere F precum și înălțimea maximă H a unui fulger din fotografie. De exemplu, fotografia de mai jos este codificată de tabloul T alăturat fotografiei .

Cerința

Scrieți un program care citește numerele N și M, cele N*M elemente ale tabloului T care codifică fotografia și rezolvă următoarele cerințe:

  1. afișează numărul maxim P de pătrate negre dispuse alăturat pe un rând în fotografie;
  2. afișează numărul F de fulgere și înălțimea maximă H a unui fulger din fotografie.

Date de intrare

Fișierul de intrare foto.in conține pe prima linie un număr natural C reprezentând cerința care trebuie rezolvată (1 sau 2). Pe a doua linie se află cele două numere naturale N și M, separate printr-un spațiu, cu semnificația din enunț. Pe fiecare dintre următoarele N linii se află câte M valori 0 sau 1, separate prin câte un spațiu, reprezentând elementele tabloului care codifică fotografia, în ordinea parcurgerii lor pe rânduri, de sus în jos, și de la stânga la dreapta în cadrul unui rând.

Date de ieșire

Fișierul de ieșire foto.out va conține, pe o singură linie:

  • dacă C=1, numărul P, reprezentând răspunsul la cerința 1;
  • dacă C=2, cele două numere F și H, în această ordine, separate printr-un singur spațiu, reprezentând
    răspunsul la cerinţa 2.

Restricții și precizări

  • N număr natural, 4 ≤ N ≤ 100
  • M număr natural, 4 ≤ M ≤ 100
  • În concurs, pentru rezolvarea cerinței 1 s-au acordat 20 de puncte, pentru rezolvarea cerinței 2 s-au acordat 70 de puncte. Pe site se acordă 10 puncte pentru exemple.

Exemplul 1

foto.in

1
6 7
0 1 0 0 1 0 0
1 0 0 0 1 0 0
0 0 1 0 0 0 1
0 1 0 0 0 1 0
0 1 0 0 1 0 0
0 0 1 0 1 0 1

foto.out

3

Explicație

Se rezolvă cerința 1. N=6, M=7. Sunt maximum P=3 pătrate negre alăturate pe rândurile 2, 3 și 4 (vezi fotografia din enunț).

Exemplul 2

foto.in

2
6 7
0 1 0 0 1 0 0
1 0 0 0 1 0 0
0 0 1 0 0 0 1
0 1 0 0 0 1 0
0 1 0 0 1 0 0
0 0 1 0 1 0 1

foto.out

5 4

Explicație

Se rezolvă cerința 2. N=6, M=7. Sunt F=5 fulgere iar înălțimea maximă a unui fulger este H=4 (vezi fotografia din enunț).

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 foto1:

#include <fstream>
#include <iostream>
using namespace std;
ifstream f("foto.in");
ofstream g("foto.out");
int T[102][102];
int main()
{
    int C,N,M;
    f>>C>>N>>M;

    if(C==1)
    {
        int x,P=0,i,j,p=0;
        for(i=1;i<=N;i++)
        { p=0;
          for(j=1;j<=M;j++)
          { f>>x;
            if(x==0)p++;
            else
              {P=max(p,P); p=0;}
          }
          P=max(P,p);
        }
        g<<P<<endl;
    }
    else
    {
      int H=0,F=0,i,j,h,r,c;
      for(r=1;r<=N;r++)
         for(c=1;c<=M;c++)
            f>>T[r][c];
      for(r=1; r<=N; r++)
       for(c=1; c<=M; c++)
          if(T[r][c]==1)
            { F++;
              i=r; j=c; h=0;
              while(T[i][j]==1)
               {   h++;
                   T[i][j]=0;
                   if(T[i+1][j]==1)i++;
                   else
                   if(T[i+1][j-1]==1){i++;j--;}
                   else
                   if(T[i+1][j+1]==1){i++; j++;}
               }
              H=max(h,H);
            }
     g<<F<<" "<<H<<endl;
    }
    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 Adresa de email.

Rezolvarea problemei #3435 foto1

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #3435 foto1 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!