Le fil d'Ariane – Qualification 2009

Level 3

É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.

Runtime constraints

Maximum memory usage
10000 kilobytes
Maximum execution time
500 milliseconds

Input/output samples

Sample input
4
4
0
0
3
0
...X
XX..
....
.XXX
Sample output
1
Sample input
4
4
0
0
3
0
...X
XXXX
....
.XXX
Sample output
0

Submit your solution

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