|
|
|
PATRONS RECTANGULARS
Imagina un rectangle de m files i n columnes dividit en quadrats tal com mostra la següent figura.
|
1 |
2 |
3 |
4 |
|
5 |
6 |
7 |
8 |
|
9 |
10 |
11 |
12 |
|
13 |
14 |
15 |
16 |
|
17 |
18 |
19 |
20 |
Cada quadrat està enumerat seqüencialment, de forma que el quadrat superior esquerra és el 1, el de la seva dreta el 2 i així successivament fins arribar al inferior dreta que és el m*n.
La següent figura mostra un rectangle amb alguns quadrats marcats:
Ara, considera la regió p*q que comença a la cantonada superior esquerra de la segona figura. Per exemple, si p = 2 i q = 1 llavors obtenim la següent regió:
Aquest patró apareix en tot el rectangle original en quatre posicions més:
Es demana fer un programa que llegeixi les dades d'un rectangle i d'una regió i calculi quantes vegades apareix la regió en el rectangle original.
No s'ha de considerar rotacions de la regió. La regió sempre es selecciona des de la cantonada superior esquerra.
Les dades d'entrada estan en el fitxer:
PATREC.IN
La primera línia d'aquest fitxer conté quatre números enters que són els valors per m (1£ m£ 20), n (1£ n£ 20), p (1£ p£ m) i q (1£ q£ n) respectivament. La següent línia és x, el nombre de quadrats marcats (0£ x£ m*n) . Cada una de les següents x línies indica la posició d'un quadrat marcat, utilitzant la numeració mostrada a la primera figura.
Les dades de sortida s'escriuran al fitxer de text:
PATREC.OUT
en el qual hi ha una sola línia que conté un número enter, el nombre de vegades en què apareix la regió dins del rectangle, incloent-hi la regió original de la cantonada superior esquerra.
S'ha de tenir en compte que un quadrat pot formar part de més d'una regió.
EXEMPLES:
|
PATREC.IN |
PATREC.OUT |
|
5 4 2 1 7 3 5 10 11 14 18 19 |
4 |
|
4 5 2 2 2 2 5 |
2 |
Tornar