Ivrogne – Regional event 2005

Level 5

ENONCE

Joseph Marchand a bu trop de ricard. Aidez-le à rentrer chez lui. Il ne peut faire plus de 3 mètres sans pouvoir 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 a 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.

CONTRAINTES

1 \<= N, P \< 100 ou N et P sont les dimensions du terrain.

ENTREE

La première ligne indique le nombre de ligne (N)

La seconde ligne indique le nombre de colonnes (P)

Les lignes suivantes décrivent la matrice.

SORTIE

La longeur du chemin.

COMMENTAIRES

Dans l'exemple ci-dessous, en empruntant ce chemin par exemple :

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

Runtime constraints

Maximum memory usage
1400 kilobytes
Maximum execution time
125 milliseconds

Input/output samples

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

Submit your solution

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