Ivrogne – Regional event 2005

Level 5

Énoncé

Joseph Marchand a bu trop de Ricard. Aidez-le à rentrer chez lui. Il ne peut faire plus de 3 mètres sans se tenir à quelque chose (lampadaire, voiture, passant, bouteille de Vodka, etc...)

Joseph ne peut pas marcher en diagonale (déjà que tout droit, ce n'est pas évident...)

Aidez-le à rentrer chez lui ! Vous devez donner le plus court chemin qu'il doit emprunter pour aller du coin haut gauche jusqu'en bas a droite.

Entrée

  • La première ligne contient un entier $L$ : le nombre de lignes
  • La seconde ligne contient un entier $C$ : le nombre de colonnes
  • Les lignes suivantes décrivent la matrice

Sortie

La longueur du chemin ou $-1$ si aucun chemin n'existe.

Contraintes

  • $L \lt 100$
  • $C \lt 100$

Runtime constraints

Maximum memory usage
1400 kilobytes
Maximum execution time
125 milliseconds

Input/output samples

Sample input
6 10
.###......
........#.
..........
.....#.#..
..........
.......#..
Sample output
14
Note

Dans cet exemple, il peut emprunter le chemin suivant :

1
2
3
4
5
6
*###......
*****...#.
....*.....
....*#.#..
....*****.
.......#**

Les croisillons représentent les objets auxquels Joseph Marchand peut se tenir. Ici, Joseph arrive à rentrer de justesse chez lui grâce à l'objet en L4C6.

Submit your solution

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