L'emacsaure – Regional event 2016

Level 3

É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

Runtime constraints

Maximum memory usage
10000 kilobytes
Maximum execution time
200 milliseconds

Input/output samples

Sample input
4 4
.X.X
..X.
...X
....
Sample output
1
Note

Dans le schéma ci-dessous, la lave est représentée par des ~.

L'emacsaure e est bloqué par la faille à droite, donc il fait un pas vers le bas, puis il avance un pas vers droite. Il refait de même encore deux fois.

1
2
3
4
eX.X    .X.X    ~X.X    ~X.X    ~~.X    ~~.X    ~~~X
..X.    e.X.    ~eX.    ~.X.    ~~X.    ~~X.    ~~~.
...X    ...X    ~..X    ~e.X    ~~eX    ~~.X    ~~~X
....    ....    ~...    ~...    ~~..    ~~e.    ~~~e
Sample input
5 5
.X...
X....
.....
.....
.....
Sample output
0
Note

Le pauvre emacsaure est bloqué dès le début.

1
2
3
4
5
eX...    ~X...
X....    ~....
.....    ~....
.....    ~....
.....    ~....
Sample input
2 4
.X..
...X
Sample output
0
Note

L'emacsaure finit bloqué par la dernière faille et le côté inférieur du terrain.

1
2
eX..    .X..    ~X..    ~X..    ~~..    ~~~.
...X    e..X    ~e.X    ~.eX    ~~eX    ~~~X

Submit your solution

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