Le fil d'Ariane – Qualification 2009

Énoncé¶

TTY, la chatte mythique de Prologin, est perdue dans le campus de Polytechnique. Celui-ci est donné sous la forme d'un labyrinthe rectangulaire de H*L cases, où une case est soit vide, soit un mur infranchissable. Une gamelle se trouve dans le labyrinthe. Votre tâche est de rassurer, le cas échéant, TTY : pourra-t-elle ou non atteindre sa gamelle ? Vous devez donc écrire un programme qui, étant donné la position de TTY, la position de sa gamelle, et le labyrinthe, renvoie si elle peut ou non atteindre sa gamelle.

Contraintes¶

• 1 <= H <= 500
• 1 <= L <= 500

Entrée¶

• Sur les deux premières lignes, deux entiers : H et L, respectivement la hauteur et la largeur du labyrinthe.
• Sur deux lignes suivantes, deux entiers : y_tty et x_tty, la position de départ de tty (la ligne, puis la colonne).
• Ensuite, encore sur deux lignes, deux entiers : y_gam et x_gam, la position de la gamelle (la ligne, puis la colonne).
• Et enfin, sur les H lignes suivantes, L caractères : '.' ou 'X', représentant respectivement une case vide et un mur infranchissable. Note : La case (0,0) est située en haut à gauche. TTY ne peut se déplacer que verticalement et horizontalement.

Sortie¶

Un entier, 1 ou 0, indiquant si oui ou non TTY peut atteindre sa gamelle.