Cerința

Se dă o matrice pătratică de ordin p şi alta cu m linii şi n coloane, ale căror elemente sunt egale cu 0, 1 sau 2. Determinaţi numărul de apariţii ale primei matrice în a doua.

Date de intrare

Fișierul de intrare zoom.in conține pe prima linie numerele p,m,n, pe următoarele p linii câte p numere naturale, iar pe următoarele m linii câte n numere naturale, reprezentând elementele celor două matrice.

Date de ieșire

Fișierul de ieșire zoom.out va conține pe prima linie numărul de apariţii ale primei matrice în a doua.

Restricții și precizări

2 ≤ m , n ≤ 1000
1 ≤ p ≤ 10
p ≤ m şi p ≤ n
elementele matricelor sunt 0,1 sau 2
prima matrice apare în a doua dacă există o submatrice în a doua ale cărei elemente să coincidă cu ale primei matrice

Exemplu

zoom.in

zoom.out

Explicație

Prima matrice apare în a doua în trei poziţii astfel încât colţul stânga sus al său să coincidă pe rând cu elementele din a doua matrice situate în poziţiile (1,3),(2,1),(3,4).

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

#include <fstream>

using namespace std;
ifstream f("zoom.in");
ofstream g("zoom.out");

short int a[1001][1001];
long long put[11] , val[1001], va[11] , x ;
long p , m , n , i , j , nr , ok , k ;

int main()
{
    f >> p >> m >> n ;
    put[0]=1 ;
    for ( i=1 ; i<=p ; i++ ) put[i]=put[i-1]*3 ;

    for ( i=1 ; i<=p ; i++ )
       for ( j=1 ; j<=p ; j++ )
        {
            f >> x ;
            va[j] += x*put[i-1] ;

        }
    for( i=1 ; i<=p-1 ; i++ )
    {
        for( j=1; j<=n ; j++ )
        {
            f >> a[i][j] ;
            val[j] += a[i][j]*put[i-1] ;
        }
    }
    for( j=1 ; j<p ; j++ )
    {
       f >> a[p][j] ;
       val[j] += a[p][j]*put[p-1] ;
    }
    for( j=p ; j<=n ; j++ )
    {
       f >> a[p][j] ;
       val[j] += a[p][j]*put[p-1] ;
       ok=1 ;
       for ( k=p ; k>=1 ; k-- )
         if ( va[k]!=val[j+k-p]){ ok=0 ; break ; }
       nr +=ok ;
    }

    for ( i=p+1 ; i<=m ; i++ )
    {

       for( j=1 ; j<p ; j++ )
       {
          f >> a[i][j] ;
          val[j] = ( val[j]-a[i-p][j])/3+a[i][j]*put[p-1] ;

       }
       for( j=p ; j<=n ; j++ )
       {
          f >> a[i][j] ;
          val[j] = ( val[j]-a[i-p][j])/3+a[i][j]*put[p-1] ;
          ok=1 ;
          for ( k=p ; k>=1 ; k-- )
            if ( va[k]!=val[j+k-p]){ ok=0 ; break ; }
          nr +=ok ;
       }
    }
    g << nr ;
    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 #1527 zoom

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