L'emacsaure – Regional event 2016

Énoncé¶

Un emacsaure veut échapper à une coulée de lave qui ravage la plaine. Il prend donc ses pattes à son cou et se met à courir devant la coulée. Sportif, notre emacsaure est deux fois plus rapide que la lave. Toutefois, sa course est parsemée de failles qu'il doit absolument contourner.

Le terrain est représenté par une grille rectangulaire bordée de failles (non représentées) en haut et en bas. L'emacsaure commence sa course au coin en haut à gauche de la carte aux coordonnées (0, 0). La lave se situe à gauche de l'emacsaure, à l'abscisse -1. Ils évoluent vers la droite.

Chaque fois que l'emacsaure effectue deux déplacements, la lave avance d'une unité pour recouvrir l'intégralité de la colonne suivante. Le déplacement de la lave est indépendant de la présence de failles.

L'emacsaure agit de la manière suivante :

• s'il n'y a pas de faille devant lui, alors il avance tout droit, vers la droite ;
• si une faille l'empêche d'avancer, mais que la case juste en-dessous de lui est libre, il s'y déplace ;
• sinon il est bloqué et la lave finit par le rattraper.

Votre but est d'écrire un programme déterminant si l'emacsaure parvient ou non à s'échapper, c'est-à-dire à atteindre la dernière colonne du terrain.

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 X indique une faille.

La case aux coordonnées (0, 0), où l'emacsaure se trouve initialement, ne sera jamais une faille.

Sortie¶

Un unique entier, 1 si l'emacsaure parvient à s'échapper, 0 sinon.

Contraintes¶

• 1 ≤ m ≤ 1 000
• 1 ≤ n ≤ 1 000