Ne pas se jeter dedans – Regional event 2009

Level 3

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.

Runtime constraints

Maximum memory usage
2048 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

Sample input
10
10
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 1 1 1 1 0 0 0
0 0 0 0 1 1 1 1 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 1
0 8
Sample output
1

Submit your solution

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