Mots mêlés – Qualification 2008

Level 4

Énoncé

Vous connaissez certainement ce jeu classique : les mots mêlés. Pour rappel, il s'agit de trouver des mots disposés horizontalement ou verticalement dans une grille remplie de lettres. Les informaticiens étant d'infatigables paresseux, il serait pratique d'avoir un programme qui fait la recherche à votre place.
Vous devez donc écrire un programme qui, étant donnée une grille de N par M cases en entrée et d'un dictionnaire de P mots, renvoie le nombre de mots trouvés dans la grille.

Contraintes

1 <= N, M, P <= 500

Entrée

  • Sur la première ligne, trois entiers : N, M, P, séparés par un espace.<
  • Sur les P lignes suivantes, la liste des mots à chercher dans la grille. Chaque mot contiendra entre 1 et 500 lettres capitales ASCII.<
  • Sur les N lignes suivantes, la grille. Chacune des lignes de la grille est une chaîne de M lettres capitales ASCII.<

Sortie

Un entier, indiquant le nombre de mots du "dictionnaire" présents dans la grille.

Commentaires

  • La grille, ainsi que les mots à chercher ne comporteront que des lettres capitales.
  • Un mot qui est trouvé plusieurs fois ne doit être compté qu'une fois.
  • Tous les mots de la liste sont différents.
  • Chaque lettre de la grille peut être utilisée sans limitation.
  • Les mots peuvent être lus dans la grille verticalement ou horizontalement, à l'endroit ou à l'envers.

Runtime constraints

Maximum memory usage
16000 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

Sample input
5 5 4
RAT
MANGER
BAZAR
CODER
BAZAR
ARTRG
ZAMAN
ATYNQ
REDOC
Sample output
3
Sample input
12 13 10
PROLOGIN
LOGIN
UNIX
LINUX
FREEBSD
WINDOWS
CAML
C
PASCAL
JAVA
ABETXINWAMDJX
UNILWNINRHREZ
GILDNIGOLQUOP
FXKNXGOISNXAZ
ENNIGOLUDNTUD
AICAMLATBFCQS
TLSBLOGINEAXB
RWDSBRIJACMLE
IILELPASCALOE
GNSWINDOWVUER
EBRDNMEPOKSDF
ALBLUQDSBJDOV
Sample output
6

Submit your solution

You have to register or log in to be able to submit your solution.