1527 - Zoom

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

2 4 5
0 1
2 1
1 2 0 1 2
0 1 2 1 2
2 1 2 0 1
1 1 1 2 1

zoom.out

3

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).

Încărcare soluție

Lipește codul aici

<syntaxhighlight lang="python" line="1">

​const fs = require('fs');

const readline = require('readline');

const rl = readline.createInterface({

 input: fs.createReadStream('zoom.in'),

 output: fs.createWriteStream('zoom.out')

});

let a = new Array(1002).fill(0).map(() => new Array(1002).fill(0));

let v = new Array(20).fill(0).map(() => new Array(20).fill(0));

rl.on('line', (line) => {

 const [x, y, z] = line.split(' ').map(Number);

 for (let i = 0; i < x; ++i) {

   const row = rl.readline().split(' ').map(Number);

   for (let j = 0; j < x; ++j) {

     v[i][j] = row[j];

   }

 }

 for (let i = 0; i < y; ++i) {

   const row = rl.readline().split(' ').map(Number);

   for (let j = 0; j < z; ++j) {

     a[i][j] = row[j];

   }

 }

 let cnt = 0;

 for (let i = 0; i <= y - x; ++i) {

   for (let j = 0; j <= z - x; ++j) {

     let ok = 0;

     for (let h = i, hi = 0; h < i + x; ++h, ++hi) {

       for (let g = j, gj = 0; g < j + x; ++g, ++gj) {

         if (a[h][g] !== v[hi][gj]) {

           ok = 1;

         }

       }

     }

     if (ok === 0) {

       cnt++;

     }

   }

 }

 rl.write(cnt.toString());

});

rl.on('close', () => {

 process.exit(0);

});

</syntaxhighlight>