Le vimétrodon – Regional event 2016

Level 5

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

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

Runtime constraints

Maximum memory usage
2000 kilobytes
Maximum execution time
2000 milliseconds

Input/output samples

Sample input
5 10
........XX
XXXX.XX.X.
.....X..X.
.....X.X..
.....X...X
Sample output
1
Note

Voici le détail de la trajectoire du vimétrodon v jusqu'à la dernière colonne, tous les deux pas. La lave est représentée par ~.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
v.......XX
XXXX.XX.X.
.....X..X.
.....X.X..
.....X...X

~.v.....XX
~XXX.XX.X.
~....X..X.
~....X.X..
~....X...X

~~..v...XX
~~XX.XX.X.
~~...X..X.
~~...X.X..
~~...X...X

~~~...v.XX
~~~X.XX.X.
~~~..X..X.
~~~..X.X..
~~~..X...X

~~~~....XX
~~~~.XXvX.
~~~~.X..X.
~~~~.X.X..
~~~~.X...X

~~~~~...XX
~~~~~XX.X.
~~~~~Xv.X.
~~~~~X.X..
~~~~~X...X

~~~~~~..XX
~~~~~~X.X.
~~~~~~..X.
~~~~~~.X..
~~~~~~v..X

~~~~~~~.XX
~~~~~~~.X.
~~~~~~~.X.
~~~~~~~X..
~~~~~~~.vX

~~~~~~~~XX
~~~~~~~~X.
~~~~~~~~X.
~~~~~~~~.v
~~~~~~~~.X
Sample input
5 10
.........X
XXXXXXXX.X
.........X
.XXXXXXXXX
..........
Sample output
0
Note

Après deux pas, la lave bloque l'unique passage vers la sortie.

1
2
3
4
5
~.v......X
~XXXXXXX.X
~........X
~XXXXXXXXX
~.........

Submit your solution

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