Prologin
2024
Attaqué par un tueur fou, Simon court vers sa voiture décapotable pour s'enfuir. L'endroit où il se trouve comporte une grande zone grillagée rectangulaire dans laquelle se trouvent plusieurs mares de mazout.
Simon n'a pas le temps de réfléchir et veut courir en ligne droite vers sa voiture. Vous devez lui dire s'il pourra y arriver ou s'il sera bloqué par le grillage.
Pour cela, l'on vous donne la position de Simon, la position de sa voiture, et la position de toutes les mares de mazout. Vous considérerez que le grillage a été construit de façon à inclure dans son enceinte toutes les mares, tout en restant d'aire minimum comme sur cet exemple :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | ...................................... ...................................... ...................................... ...........+--------X-------+......... ...........|..X.........X...|......... ...........|....X...........|......... ...........|................|......... ...O.......|............X...X....V.... ...........X................|......... ...........|.....X.....X....|......... ...........|................|......... ...........+---X------------+......... ...................................... ...................................... ...................................... |
ENTREE
Les deux premières lignes contiennent un entier n, le nombre de lignes de la carte, et un entier m, son nombre de colonnes.
Les N lignes suivantes contiennent chacune M entiers valant 0 ou 1, avec 1 representant du mazout et 0 la terre ferme.
L'avant-dernière ligne contient deux entiers représentant la position de Simon sur la carte (ligne, colonne).
La dernière ligne contient deux entiers représentant la position de la voiture de Simon sur la carte (ligne, colonne).
SORTIE
Un entier valant 1 si Simon peut atteindre sa voiture sans rencontrer les grillages autour du mazout, 0 sinon.
CONTRAINTES
0 \< N,M \<= 500. Les positions de Simon et sa voiture ne seront pas situées dans l'enceinte grillagée et seront sur une même ligne ou colonne.