Prologin
2024
Énoncé¶
Un vimétrodon veut échapper à une coulée de lave qui ravage la plaine. Il va pour cela courir ! Heureusement, il est deux fois plus rapide que la lave. Le problème est qu'il doit contourner des failles qui bloquent son chemin.
La carte est représentée par une grille, bordée de failles (non représentées) en haut et en bas. Le vimétrodon commence sa course au coin en haut à gauche de la carte, aux coordonnées (0, 0). La lave se situe juste à gauche, à l'abscisse -1, et tous les deux déplacements du vimétrodon, elle avance sur toute la colonne suivante. On ne prend pas en compte le relief du terrain dans le déplacement de la lave.
Le vimétrodon se déplace horizontalement et verticalement, mais pas en diagonale, et il ne peut pas traverser les failles.
Votre but est d'écrire un programme déterminant si le vimétrodon parvient ou non à s'échapper, c'est-à-dire atteindre la dernière colonne de la carte.
Entrée¶
L'entrée comprendra :
- sur la première ligne, les dimensions entières m et n du terrain, séparées par une espace ;
- sur les m lignes suivantes, chacune de longueur n, la carte du terrain où :
- un
.indique de la plaine ; - un
Xindique une faille.
- un
La case aux coordonnées (0, 0), à partir de laquelle le vimétrodon commence à courir, ne contient jamais de faille.
Sortie¶
Un simple entier, 1 si le vimétrodon parvient à s'échapper, 0 sinon.
Contraintes¶
- 1 ≤ m ≤ 100
- 1 ≤ n ≤ 1 000