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

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

});