Bessie est encore bloquée du mauvais côté de la grange de Farmer John. Sa mauvaise vue nécessite votre aide pour la traverser.

La grange est une grille $N \times N$ de cases carrées ($2 \leq N \leq 20$), vides ou contenant du foin infranchissable. Elle part du bas gauche $(1,1)$ vers le haut droit $N,N$. Les instructions sont « avancer », « tourner à gauche de 90 degrés », « à droite de 90 degrés ». Donnez la séquence la plus courte. Vers l’extérieur, un mur, ou le foin, elle ne bouge pas et passe à la commande suivante.

Elle ignore si elle regarde vers le haut, $(1,2)$, ou à droite, $(2,1)$. Donnez la plus courte séquence réussissant dans les deux cas. Une fois arrivée, elle ignore la suite.

Entrée

Lisez l’entrée standard.

La première ligne contient $N$.

Les $N$ suivantes ont exactement $N$ caractères décrivant la grange. Le premier de la dernière ligne est $(1,1)$, le dernier de la première est $(N,N)$.

H représente le foin, E une case vide.

$(1,1)$ et $N,N$ sont vides et un chemin vide de $(1,1)$ à $N, N$ est garanti.

Sortie

Écrivez sur la sortie standard.

Affichez une ligne avec la longueur de la plus courte séquence arrivant au but, vers le haut ou la droite au départ.

Exemples

Entrée 1

3
EHE
EEE
EEE

Sortie 1

9

Remarque

« Avancer, droite, avancer, avancer, gauche, avancer, gauche, avancer, avancer » réussit dans les deux orientations de l’exemple.

Auteur du problème : Brian Dean