Ivrogne – Épreuve régionale 2005

Niveau 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$

Contraintes d'exécution

Utilisation mémoire maximum
1400 kilo-octets
Temps d'exécution maximum
125 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
6 10
.###......
........#.
..........
.....#.#..
..........
.......#..
Exemple de sortie
14
Commentaire

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.