Porte Dérobée – Épreuve régionale 2022

Niveau 2

Énoncé

Notre cher Joseph Marchand se retrouve face à une série de portes qui lui semblent impossibles à ouvrir... Il a besoin de votre aide !

Il remarque qu'il y a sur la porte un quadrillage avec des lettres dedans, et qu'à côté de ce quadrillage, il y a une suite de lettres N, S, E, O (correspondant respectivement aux directions Nord, Sud, Est et Ouest) ainsi que des coordonnées. Il découvre aussi un petit terminal sur lequel il peut taper une suite de lettres.

Il en conclut donc que ce sont des directions à suivre à partir des coordonnées données afin de résoudre cette énigme.

Pour aider Joseph à ouvrir toutes les portes, vous devrez parcourir le chemin indiqué à partir des coordonées de départ et ensuite afficher le mot formé par les lettres situées dans les cases que vous aurez traversées.

Entrée

L’entrée contiendra

  • Sur la première ligne, un entier : H, la hauteur de la porte (elle peut être vue comme une matrice carrée).
  • Sur la ligne suivante, un entier : L, la longueur du chemin à suivre.
  • Sur les H lignes suivantes, une liste de H éléments : lettres, ce sont les lettres qui sont sur la porte.
    • Une ligne par élément de la liste : une liste de H caractères consécutifs.
  • Sur la ligne suivante, une liste de 2 entiers séparés par un espace : X et Y, ce sont les coordonnées du point de départ (le coin supérieur gauche du quadrillage correspondant à la coordonnée (0, 0)).
  • Sur la ligne suivante, une liste de L caractères consécutifs : chemin, le chemin que Joseph doit suivre pour déverrouiller la porte.

Sortie

Afficher un mot formé par le chemin que Joseph doit suivre (le mot n'a pas forcément de sens).

Contraintes

  • $4 \le H \le 15$
  • $5 \le L \le 225$

Contraintes d'exécution

Utilisation mémoire maximum
1000 kilo-octets
Temps d'exécution maximum
1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
4
7
ABCD
EFGH
IJKL
MNOP
0 0
ESOSEEN
Exemple de sortie
ABFEIJKG
Exemple d'entrée
5
12
QWERT
YUIOP
ASDFG
HJKLZ
XCVBN
3 2
NNOSEESSOONE
Exemple de sortie
FOREIOPGZLKDF
Exemple d'entrée
11
40
LCMKFQADABL
JYHSDAYKGTB
QTWLHUIKETR
VUKICIZACWS
SFLLVBNEMTR
NMREAFAATFW
KUBAHKOLNYI
ZNJBIMIGZMQ
EWZNNUTZGPN
IYUEYTEYYDG
EQUZXBOAVRB
9 7
NSNOOSNNOOSONSOSSNSSESOOONNSSEOONEOEONEE
Exemple de sortie
MYMYNLGLAAFKHAHABNBNEYXZUQYWYQUQEIYIYIEWZ